list - prolog中列表中0和1的唯一组合

Question

我有问题，因为我想生成一个列表的排列（在序言中），其中包含 n 个零和 24 - n 个没有重复的。我试过：findall(L, permutation(L,P), Bag)然后sort它删除重复，但它会导致堆栈溢出。任何人都有有效的方法来做到这一点？

Answer 1

与其考虑列表，不如考虑二进制数。该列表的长度为 24 个元素。如果所有这些元素都是 1，我们有：

?- X is 0b111111111111111111111111.
X = 16777215.

事实标准谓词between/3可用于在区间内生成数字[0, 16777215]：

?- between(0, 16777215, N).
N = 0 ;
N = 1 ;
N = 2 ;
...

这些数字中只有一部分满足您的条件。因此，您需要过滤/测试它们，然后将传递的数字转换为其二进制等效项的列表表示。

Answer 2

按升序选择 0 到 23 之间的 n 个随机数。这些整数为您提供零的索引，并且所有配置都不同。关键是生成这些索引列表。

%
% 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,_,_,[]). 

现在我们可以从可用的可能索引中获取索引列表。

例如：

给我从 0 到 23（含）的 5 个索引：

?- 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] ;
...

全部给他们：

?- 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.

我们期待： (24! / ((24-5)! * 5!)) 解决方案。

的确：

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

现在唯一的问题是将每个解决方案都转换[0, 1, 2, 3, 4]为 0 和 1 的字符串。这留作练习！

Answer 3

这是直接生成字符串的更简单的答案。很直接。

need_list(ZeroCount,OneCount,Sol) :- 
   length(Zs,ZeroCount),maplist([X]>>(X='0'),Zs),
   length(Os,OneCount),maplist([X]>>(X='1'),Os),
   compose(Zs,Os,Sol).

compose([Z|Zs],[O|Os],[Z|More]) :- compose(Zs,[O|Os],More).
compose([Z|Zs],[O|Os],[O|More]) :- compose([Z|Zs],Os,More).
compose([],[O|Os],[O|More])     :- !,compose([],Os,More).
compose([Z|Zs],[],[Z|More])     :- !,compose(Zs,[],More).
compose([],[],[]).

rt(ZeroCount,Sol) :- 
   ZeroCount >= 0,
   ZeroCount =< 24,
   OneCount is 24-ZeroCount,   
   need_list(ZeroCount,OneCount,SolList),
   atom_chars(Sol,SolList).

?- rt(20,Sol).
Sol = '000000000000000000001111' ;
Sol = '000000000000000000010111' ;
Sol = '000000000000000000011011' ;
Sol = '000000000000000000011101' ;
Sol = '000000000000000000011110' ;
Sol = '000000000000000000100111' ;
Sol = '000000000000000000101011' ;
Sol = '000000000000000000101101' ;
Sol = '000000000000000000101110' ;
Sol = '000000000000000000110011' ;
Sol = '000000000000000000110101' ;
....

?- findall(Collected,rt(5,Collected),L),length(L,LL).   
L = ['000001111111111111111111', '000010111111111111111111', '000011011111111111111111', '000011101111111111111111', '000011110111111111111111', '000011111011111111111111', '000011111101111111111111', '000011111110111111111111', '000011111111011111111111'|...],
LL = 42504.