All binary numbers with exactly n digits

Question

I need a predicate to produce all binary numbers with length N in a list.

Sample use:

?- bins(2,L).
L = [[0,0], [0,1], [1,0], [1,1]].    % expected result

score 3 · Answer 1 · edited May 23 '17 at 12:17

3

No need to use findall/3!

We define bins/2 based on clpfd, foldl/4, Prolog lambdas, if_/3, and (#<)/3.

:- use_module(library(lambda)).
:- use_module(library(clpfd)).

bins(N,Zss) :-
   if_(N #< 1,
       ( N #= 0, Zss = [[]] ),
       ( N #= N0+1,
         bins(N0,Xss),
         foldl(\Bs^phrase(([[0|Bs]],[[1|Bs]])),Xss,Zss,[]))).

Sample use:

?- bins(4,Zss).
Zss = [[0,0,0,0],[1,0,0,0],[0,1,0,0],[1,1,0,0],
       [0,0,1,0],[1,0,1,0],[0,1,1,0],[1,1,1,0],
       [0,0,0,1],[1,0,0,1],[0,1,0,1],[1,1,0,1],
       [0,0,1,1],[1,0,1,1],[0,1,1,1],[1,1,1,1]].

Here is the most general query:

?- bins(N,Zss).
  N = 0, Zss = [[]]
; N = 1, Zss = [[0],[1]]
; N = 2, Zss = [[0,0],[1,0],[0,1],[1,1]]
; N = 3, Zss = [[0,0,0],[1,0,0],[0,1,0],[1,1,0],[0,0,1],[1,0,1],[0,1,1],[1,1,1]]
...

edited May 23 '17 at 12:17

Community

1
1

answered Aug 13 '15 at 19:01

repeat

18,496
4
54
166

Note the anomaly: `bins(1+0,L)` fails, whereas `bins(2+0,L)` succeeds – false Aug 15 '15 at 09:32
New version improves even upon determinism! – false Aug 15 '15 at 16:10
@false. And `N = 0, Zss = [[]]` as base-case, not `N = 1, Zss = [[0],[1]]`. Somewhat more canonical, is it not? – repeat Aug 15 '15 at 16:29
... you mean: well-founded – false Aug 15 '15 at 18:07
@false. Ah... yes, exactly! It *was* on the tip of me tongue. – repeat Aug 15 '15 at 18:13

score 2 · Answer 2 · answered Dec 28 '11 at 06:13

2

There are probably better ways, but here is a solution using findall

bins(N,L) :-
    findall(Num,binary_number(N,Num),L).

binary_number(0,[]).
binary_number(N,[D|Ds]) :-
    N > 0,
    member(D,[0,1]),
    N1 is N - 1,
    binary_number(N1,Ds).

answered Dec 28 '11 at 06:13

cth

414
2
3

1

i need a solution without findall – user1118501 Jan 09 '12 at 00:08

m09 · Answer 3 · 2011-12-28T14:07:14.000

0

Alternatively :

member_(A, B) :- member(B, A).
bins(Size, Result) :-
    findall(L, (length(L, Size), maplist(member_([0, 1]), L)), Result).

Could be simplified with the use of the lambda module :

bins(Size, Result) :-
    findall(L, (length(L, Size), maplist(\X^member(X, [0, 1]), L)), Result).

edited Dec 28 '11 at 14:07

answered Dec 28 '11 at 13:49

m09

7,490
3
31
58

i need a solution without findall or other "ready" predicates – user1118501 Jan 09 '12 at 00:09

All binary numbers with exactly n digits

3 Answers3