prolog all binary numbers

问题:

i need a predicate that will produce all the binary number of N digits .

For instance the predicate binary(2,L)

will return L = [[0, 0], [0, 1], [1, 0], [1, 1]].

please do not use findall ....

回答1:

Once you have a list representing all the numbers with N bits, generating all the numbers of N+1 bits is just a matter of unfolding every N-number [a,b,c,...] into two N+1-numbers: [0,a,b,c,...] and [1,a,b,c,...].

Update:

unfold([], []).
unfold([H|T], [[0|H], [1|H]|L]) :-
   unfold(T, L).

bn(N, L) :-
   (   N = 0
   ->  L = [[]]
   ;   N1 is N - 1,
       bn(N1, L1),
       unfold(L1, L)
   ).

回答2:

If you need to avoid findall/3, then you need an aggregator to collect the binary numbers:

binary(N, L) :-
  collect_binaries(N, [], L).

You then generate one binary at a time and check whether it's already present in the aggregated list:

collect_binaries(N, R, L) :-
  length(B, N),
  make_binary(B), % make binary of length N
  \+ memberchk(B, R),
  !,
  collect_binaries(N, [B|R], L).

If generating another binary fails, you are done:

collect_binaries(_, L, L).

Generating binaries is simple (I'm using the format you gave in your question: a list of 0/1 values). You iterate over all positions in the list and use either 1 or 0:

make_binary([]).
make_binary([H|T]) :-
  member(H, [1,0]),
  make_binary(T).

Result:

?- binary(2, L).
L = [[0, 0], [0, 1], [1, 0], [1, 1]]
Yes (0.00s cpu)