Prolog如何实现含重复元素列表的无重复输出全排列

实现逻辑 #

内置permutation/2会把值相同的元素判定为不同独立元素，因此会生成重复排列结果。我们可以通过自定义元素选择逻辑，每次选取排列首元素时相同值仅选一次，从生成路径上避免重复结果，无需额外对最终结果去重。

完整实现代码 #

% 对外暴露的去重排列谓词
newPermutation([], []).
newPermutation(List, [X|RestPerm]) :-
    select_unique(X, List, RestList),
    newPermutation(RestList, RestPerm).

% 辅助谓词：相同值的元素仅选取第一个，跳过后续重复值
select_unique(Element, [Element|Tail], Tail).
select_unique(Element, [Head|Tail], [Head|RestTail]) :-
    dif(Element, Head),
    select_unique(Element, Tail, RestTail).

运行效果 #

执行查询newPermutation([0,1,1], L).，输出结果完全符合预期：

L = [0, 1, 1] ;
L = [1, 0, 1] ;
L = [1, 1, 0] ;
false.

内容的提问来源于stack exchange，提问作者Andrius