序言列表中 0 和 1 的唯一组合

Question

我有问题，因为我想生成列表的排列（在 prolog 中），其中包含 n 个零和 24 - n 个无重复的 1。我试过：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 ;
...

这些数字中只有一部分符合您的条件。因此，您将需要 filter/test 它们，然后将传递的数字转换为其二进制等价物的列表表示形式。

Answer 2

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

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

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

例如：

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

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

序言列表中 0 和 1 的唯一组合

Unique combinations of 0 and 1 in list in prolog

list

permutation

prolog

non-repetitive