Prolog：如何在不重复的情况下创建所有可能的组合

Question

我正在尝试创建一个谓词来查找所有可能的组合而不重复相同的数字。我尝试使用排列谓词，但它发现了重复的列表。例如：

permutation([0,1,1], L).
L = [0,1,1];
L = [0,1,1];
L = [1,0,1];
L = [1,1,0];
L = [1,0,1];
L = [1,1,0];

我需要的：

newPermutation([0,1,1], L).
L = [0,1,1];
L = [1,0,1];
L = [1,1,0];

有人可以帮我吗？多谢...

Answer 1

对于地面列表，您可以按照@GuyCoder的建议进行操作：distinct(permutation([1,1,0],L)).

对于任意列表，您可以借助以下方法枚举所有不同的解决方案dif/2：

permutation_no_dup([], []).
permutation_no_dup(L, PL):-
  same_length(L, PL),
  length(L, Len),
  numlist(1,Len, RLMax),
  reverse(RLMax, LMax),
  length(LCur, Len),
  maplist(=(1), LCur),
  permutation_no_dup(LCur, L, LMax/LCur-L, [], PL).
  
permutation_no_dup([], _, _, PL, PL).
permutation_no_dup([], _, LMax/LCur-L, PL, PL1):-
  dif(PL, PL1),
  next(LCur, LMax, NLCur),
  permutation_no_dup(NLCur, L, LMax/NLCur-L, [], PL1).
permutation_no_dup([Take|LCur], L, Info, PL, PL1):-
  nth1(Take, L, Item, L1),
  permutation_no_dup(LCur, L1, Info, [Item|PL], PL1).

next([Cur|LCur], [Max|_], [NCur|LCur]):-
  Cur < Max,
  succ(Cur, NCur).
next([Cur|LCur], [Cur|LMax], [1|NLCur]):-
  next(LCur, LMax, NLCur).

same_length([],[]).
same_length([_|Xs], [_|Ys]) :-
   same_length(Xs, Ys).

示例运行：

?- permutation_no_dup([0,1,1], L).
L = [1, 1, 0] ;
L = [1, 0, 1] ;
L = [0, 1, 1] ;
false.
?- permutation_no_dup([X,Y], L), X=Y.
X = Y,
L = [Y, Y] ;
false.

更新：

通过上面的代码，我在 SWI 8.0.2 中得到了这个输出，这显然是错误的：

?- permutation_no_dup([x,y,Z,Z],P), P=[x,y,z,z].
false.

?- P=[x,y,z,z], permutation_no_dup([x,y,Z,Z],P).
P = [x, y, z, z],
Z = z ;
false.

但重新安排dif/2第二个子句中的调用permutation_no_dup/5，现在显示为：

permutation_no_dup([], _, _, PL, PL).
permutation_no_dup([], _, LMax/LCur-L, PL, PL1):-
%      dif(PL, PL1),    % <-- removed dif/2 from here
  next(LCur, LMax, NLCur),
  permutation_no_dup(NLCur, L, LMax/NLCur-L, [], PL1),
  dif(PL, PL1).         % <-- Moved dif/2 to here
permutation_no_dup([Take|LCur], L, Info, PL, PL1):-
  nth1(Take, L, Item, L1),
  permutation_no_dup(LCur, L1, Info, [Item|PL], PL1).

现在我们得到：

?- permutation_no_dup([x,y,Z,Z],P), P=[x,y,z,z].
Z = z,
P = [x, y, z, z] ;
false.

?- P=[x,y,z,z], permutation_no_dup([x,y,Z,Z],P).
P = [x, y, z, z],
Z = z ;
false.