prolog - 列表元素的排列组合 - Prolog

Question

如何生成列表元素的所有可能组合？

例如，给定列表[1,2,3]，我想设计一个具有comb([1,2,3], L)形式的谓词。 应该返回以下 L 的答案:

[1]  
[2]  
[3]  
[1,2]  
[2,1]  
[1,3]  
[3,1]  
[2,3] 
[3,2]  
[1,2,3]  
[1,3,2]  
[2,1,3]  
[2,3,1]  
[3,1,2]  
[3,2,1] 

Answer 1

您要求的内容涉及列表的组合(选择子集)和排列(重新排列顺序)。

您的示例输出意味着空列表不被视为有效的解决方案，因此我们将在接下来的实现中将其排除。重新考虑这是否是一个疏忽。此外，此实现以与示例输出不同的顺序生成解决方案。

comb(InList,Out) :-
    splitSet(InList,_,SubList),
    SubList = [_|_],     /* disallow empty list */
    permute(SubList,Out).

splitSet([ ],[ ],[ ]).
splitSet([H|T],[H|L],R) :-
    splitSet(T,L,R).
splitSet([H|T],L,[H|R]) :-
    splitSet(T,L,R).

permute([ ],[ ]) :- !.
permute(L,[X|R]) :-
    omit(X,L,M),
    permute(M,R).

omit(H,[H|T],T).
omit(X,[H|L],[H|R]) :-
    omit(X,L,R).

与 Amzi 一起测试!序言:

?- comb([1,2,3],L).

L = [3] ;

L = [2] ;

L = [2, 3] ;

L = [3, 2] ;

L = [1] ;

L = [1, 3] ;

L = [3, 1] ;

L = [1, 2] ;

L = [2, 1] ;

L = [1, 2, 3] ;

L = [1, 3, 2] ;

L = [2, 1, 3] ;

L = [2, 3, 1] ;

L = [3, 1, 2] ;

L = [3, 2, 1] ;
no