[SOLVED] Unique combinations of 0 and 1 in list in prolog

Unique combinations of 0 and 1 in list in prolog

I have problem, because I want to generate permutations of a list (in prolog), which contains n zeros and 24 - n ones without repetitions. I've tried:findall(L, permutation(L,P), Bag) and then sort it to remove repetitions, but it causes stack overflow. Anyone has an efficient way to do this?

Solution

Select n random numbers between 0 and 23 in ascending order. These integers give you the indexes of the zeroes and all the configurations are different. The key is generating these list of indexes.

%
% We need N monotonically increasing integer numbers (to be used
% as indexes) from [From,To].
%

need_indexes(N,From,To,Sol) :-
   N>0,
   !,
   Delta is To-From+1,
   N=<Delta,               % Still have a chance to generate them all
   N_less is N-1,
   From_plus is From+1,
   (
      % Case 1: "From" is selected into the collection of index values
      (need_indexes(N_less,From_plus,To,SubSol),Sol=[From|SubSol])
      ;
      % Case 2: "From" is not selected, which is only possible if N<Delta
      (N<Delta -> need_indexes(N,From_plus,To,Sol))      
   ).

need_indexes(0,_,_,[]).

Now we can get list of indexes picked from the available possible indexes.

For example:

Give me 5 indexes from 0 to 23 (inclusive):

?- need_indexes(5,0,23,Collected).
Collected = [0, 1, 2, 3, 4] ;
Collected = [0, 1, 2, 3, 5] ;
Collected = [0, 1, 2, 3, 6] ;
Collected = [0, 1, 2, 3, 7] ;
...

Give them all:

?- findall(Collected,need_indexes(5,0,23,Collected),L),length(L,LL).
L = [[0, 1, 2, 3, 4], [0, 1, 2, 3, 5], [0, 1, 2, 3, 6], [0, 1, 2, 3, 7], [0, 1, 2, 3|...], [0, 1, 2|...], [0, 1|...], [0|...], [...|...]|...],
LL = 42504.

We are expecting: (24! / ((24-5)! * 5!)) solutions.

Indeed:

?- L is 20*21*22*23*24 / (1*2*3*4*5).
L = 42504.

Now the only problem is transforming every solution like [0, 1, 2, 3, 4] into a string of 0 and 1. This is left as an exercise!