使用上面的代码，我得到SWI 8.0.2的输出，这显然是错误的:
我试图创建一个谓词，找到所有可能的组合，而不重复相同的数字。我尝试使用置换谓词，但它发现了重复的列表。例如:
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];
[0, 1, 1]的无重复排列是列表[0]和[1, 1]的可能交错:
?- list_list_interleaving([0], [1, 1], Interleaving).
Interleaving = [0, 1, 1] ;
Interleaving = [1, 0, 1] ;
Interleaving = [1, 1, 0] ;
false.
可以定义为:
list_list_interleaving([], Ys, Ys).
list_list_interleaving([X | Xs], [], [X | Xs]).
list_list_interleaving([X | Xs], [Y | Ys], [X | Interleaving]) :-
list_list_interleaving(Xs, [Y | Ys], Interleaving).
list_list_interleaving([X | Xs], [Y | Ys], [Y | Interleaving]) :-
list_list_interleaving([X | Xs], Ys, Interleaving).
对于多于两个不同的元素，我们需要能够将列表中的所有列表相互交错:
lists_interleaving([Xs], Xs).
lists_interleaving([Xs, Ys | Lists], Interleaving) :-
lists_interleaving([Ys | Lists], Interleaving0),
list_list_interleaving(Xs, Interleaving0, Interleaving).
例如:
?- lists_interleaving([[a, a], [b], [c, c]], Interleaving).
Interleaving = [a, a, b, c, c] ;
Interleaving = [a, b, a, c, c] ;
Interleaving = [a, b, c, a, c] ;
Interleaving = [a, b, c, c, a] ;
Interleaving = [b, a, a, c, c] ;
Interleaving = [b, a, c, a, c] ;
Interleaving = [b, a, c, c, a] ;
Interleaving = [b, c, a, a, c] ;
Interleaving = [b, c, a, c, a] ;
Interleaving = [b, c, c, a, a] ;
Interleaving = [a, a, c, b, c] ;
Interleaving = [a, c, a, b, c] ;
Interleaving = [a, c, b, a, c] ;
Interleaving = [a, c, b, c, a] ;
Interleaving = [c, a, a, b, c] ;
Interleaving = [c, a, b, a, c] ;
Interleaving = [c, a, b, c, a] ;
Interleaving = [c, b, a, a, c] ;
Interleaving = [c, b, a, c, a] ;
Interleaving = [c, b, c, a, a] ;
Interleaving = [a, a, c, c, b] ;
Interleaving = [a, c, a, c, b] ;
Interleaving = [a, c, c, a, b] ;
Interleaving = [a, c, c, b, a] ;
Interleaving = [c, a, a, c, b] ;
Interleaving = [c, a, c, a, b] ;
Interleaving = [c, a, c, b, a] ;
Interleaving = [c, c, a, a, b] ;
Interleaving = [c, c, a, b, a] ;
Interleaving = [c, c, b, a, a] ;
false.
这里的关键观察是，交错并不等同于在任意位置插入元素:交错保持列表中元素的相对顺序。所以第一次出现的a总是在第二次出现的a之前。如果将元素标记为
?- list_list_interleaving([a1, a2], [b1, b2], Interleaving).
Interleaving = [a1, a2, b1, b2] ;
Interleaving = [a1, b1, a2, b2] ;
Interleaving = [a1, b1, b2, a2] ;
Interleaving = [b1, a1, a2, b2] ;
Interleaving = [b1, a1, b2, a2] ;
Interleaving = [b1, b2, a1, a2] ;
false.
a1总是在a2之前，b1总是在b2之前。
因此，如果我们的输入被分隔成这样一个列表的列表，我们就可以做我们需要做的事情。这是原始列表元素的多集。我们可以这样计算多集:
list_multiset([], []).
list_multiset([X | Xs], Multiset) :-
list_multiset(Xs, Multiset0),
( ClassX = [X | _],
select(ClassX, Multiset0, MultisetWithoutClassX)
-> Multiset = [[X | ClassX] | MultisetWithoutClassX]
; Multiset = [[X] | Multiset0] ).
例如:
?- list_multiset([a, b, c, a, c], Multiset).
Multiset = [[a, a], [b], [c, c]].
那么不同的排列(组合，无论什么)是一个列表的多集表示的交错:
distinct_permutation(List, Permutation) :-
must_be(ground, List),
list_multiset(List, Multiset),
lists_interleaving(Multiset, Permutation).
如此:
?- distinct_permutation([0, 1, 1], Permutation).
Permutation = [0, 1, 1] ;
Permutation = [1, 0, 1] ;
Permutation = [1, 1, 0] ;
false.
它比slaggo的解决方案快得多，但到目前为止只适用于地面列表:
?- time(aggregate_all(count, distinct_permutation([1,1,1,2,2,2,3,3,3,3,4,4,4,4,4],P), C)).
% 63,090,949 inferences, 3.958 CPU in 3.958 seconds (100% CPU, 15941609 Lips)
C = 12612600.
仍然处理包含变量的列表。所有这些繁重的工作都是由select/3完成的。我们所需要的只是"只是"。实现一个类似于memberd_t/3的select_t/4。不幸的是，到目前为止我还没有做到这一点。建议非常受欢迎，或者有人采取这种方法并运行它。
编辑:现在完全纯支持任意列表我上面想得太复杂了:不需要select/3，也不需要任何具体化的版本。上面的版本使用select/3作为关系(操作上)将元素添加到multiset中:如果已经存在包含X的等价类，则由另一个X元素扩展它，而如果没有这样的类，则添加一个新类[X]。
但是我们也可以更直接地写:
list_multiset([], []).
list_multiset([X | Xs], Multiset) :-
list_multiset(Xs, Multiset0),
multiset_elem_inserted(Multiset0, X, Multiset).
multiset_elem_inserted([], X, [[X]]).
multiset_elem_inserted([[X|Xs] | Classes], X, [[X,X|Xs] | Classes]).
multiset_elem_inserted([[Y|Ys] | Classes0], X, [[Y|Ys] | Classes]) :-
dif(X, Y),
multiset_elem_inserted(Classes0, X, Classes).
这将正确地处理变量，通过回溯来枚举约束列表中=/2或dif/2的任何项对的所有可能方法:
?- list_multiset([X, Z, X, Y], Multiset).
X = Z, Z = Y,
Multiset = [[Y, Y, Y, Y]] ;
X = Y,
Multiset = [[Y, Y, Y], [Z]],
dif(Z, Y) ;
Z = Y,
Multiset = [[Y, Y], [X, X]],
dif(X, Y),
dif(X, Y) ;
X = Z,
Multiset = [[Y], [Z, Z, Z]],
dif(Z, Y),
dif(Z, Y),
dif(Z, Y) ;
Multiset = [[Y], [X, X], [Z]],
dif(X, Y),
dif(X, Y),
dif(Z, Y),
dif(Z, X) ;
false.
这也适用于不同的排列(我们现在可以从distinct_permutation中删除must_be):
?- distinct_permutation([X, Y], Permutation).
X = Y,
Permutation = [Y, Y] ;
Permutation = [Y, X],
dif(X, Y) ;
Permutation = [X, Y],
dif(X, Y) ;
false.
?- distinct_permutation([X, Y], Permutation), X = Y.
X = Y,
Permutation = [Y, Y] ;
false.
?- distinct_permutation([X, Y], Permutation), dif(X, Y).
Permutation = [Y, X],
dif(X, Y),
dif(X, Y) ;
Permutation = [X, Y],
dif(X, Y),
dif(X, Y) ;
false.
对于地面列表，您可以按照@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.
但是在permutation_no_dup/5的第二个子句中重新安排对dif/2的调用，所以它现在读为:
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.