列表元素的排列组合 - Prolog [英] Permuted combinations of the elements of a list - Prolog

问题描述

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

How can I generate all the possible combinations of the elements of a list?

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

For example, given the list [1,2,3], I want to design a predicate with the form comb([1,2,3], L). which should return the following answer for 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] 

推荐答案

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

What you are asking for involves both combinations (selecting a subset) and permutations (rearranging the order) of a list.

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

Your example output implies that the empty list is not considered a valid solution, so we will exclude it in the implementation that follows. Reconsider if this was an oversight. Also this implementation produces the solutions in a different order than your example output.

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 测试！序言:

Tested with Amzi! Prolog:

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

这篇关于列表元素的排列组合 - Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！