列表元素的置换组合 - 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

Answer 2

保持纯洁的定义comb/2基础上same_length/2，prefix/2，foldl/4和 select/3：

梳（As，Bs）：-
   same_length（As，Full），
   Bs = [_ | _]，
   前缀（Bs，Full），
   foldl（select，Bs，As，_）。

这是OP给出的示例查询：

?- comb([1,2,3],Xs).
  Xs = [1]
; Xs = [2]
; Xs = [3]
; Xs = [1,2]
; Xs = [1,3]
; Xs = [2,1]
; Xs = [2,3]
; Xs = [3,1]
; Xs = [3,2]
; Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

好！但是，如果作为第一个参数给出的列表包含重复项怎么办？

?- comb([1,1,2],Xs).
  Xs = [1]
; Xs = [1]                   % (redundant)
; Xs = [2]
; Xs = [1,1]
; Xs = [1,2]
; Xs = [1,1]                 % (redundant)
; Xs = [1,2]                 % (redundant)
; Xs = [2,1]
; Xs = [2,1]                 % (redundant)
; Xs = [1,1,2]
; Xs = [1,2,1]
; Xs = [1,1,2]               % (redundant)
; Xs = [1,2,1]               % (redundant)
; Xs = [2,1,1]
; Xs = [2,1,1]               % (redundant)
; false.

不完全的！我们可以摆脱以上多余的答案吗？是的，只需使用selectd/3！

梳（As，Bs）：-
   same_length（As，Full），
   Bs = [_ | _]，
   前缀（Bs，Full），
   foldl（selected，Bs，As，_）。

因此，让我们通过改进的实现再次在查询之上运行comb/2！

?- comb([1,1,2],Xs).
  Xs = [1]
; Xs = [2]
; Xs = [1,1]
; Xs = [1,2]
; Xs = [2,1]
; Xs = [1,1,2]
; Xs = [1,2,1]
; Xs = [2,1,1]
; false.