列表元素的排列组合 - Prolog

Question

列表元素的排列组合 - Prolog

10

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

例如，给定列表[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]

- Simon

1

[1] 通常不被称为 [1,2,3] 的组合：我猜这不是你的意思。 - Charles Stewart

4个回答

5

通过基于 same_length/2, prefix/2, foldl/4 和 select/3 定义comb/2，以保证其纯净性:

comb(As,Bs) :-
   same_length(As,Full),
   Bs = [_|_],
   prefix(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！

comb(As,Bs) :-
   same_length(As,Full),
   Bs = [_|_],
   prefix(Bs,Full),
   foldl(selectd,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.

- repeat

4

很好的解决方案，点赞！我希望我们很快能看到一个包含所有这些纯元谓词的库！library(purple): 纯Prolog库（基本）？ - mat

注意：这需要 :- use_module(library(lists)). 和 if_/3。 - Guy Coder

@GuyCoder。你说得对。if_/3的依赖性不是立即可见的，但我链接到了selectd/3的定义...这样可以吗？ - repeat

@程序员小伙伴们，你有什么建议吗？提问者可能希望得到自包含的答案，以便轻松地重现实验（如答案中所示）。但是如何做到这一点（使用不同的Prolog系统、库等）呢？ - repeat

我查看这个答案的原因是因为我正在为测试用例生成数据，当集合中有3个或更多项时，组合和排列可以正常工作，但当集合中只有2个项且我需要生成一个包含3个项的模式时，我该如何扩展集合。这个答案似乎有我所需的内容，现在只需要检查一下。 - Guy Coder

2

有一个预定义的谓词叫作permutation，它可以用于检查两个列表是否是排列关系。

1 ?- permutation([1,2,3],L).
L = [1, 2, 3] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [1, 3, 2] ;
L = [3, 1, 2] ;
L = [3, 2, 1] .

2 ?- listing(permutation).
lists:permutation([], [], []).
lists:permutation([C|A], D, [_|B]) :-
        permutation(A, E, B),
        select(C, D, E).

lists:permutation(A, B) :-
        permutation(A, B, B).

true.

希望这可以帮助您...

- AhmadAssaf

1

这对于了解如何描述排列是绝对有帮助的（+1！）。这段代码的一个教学特点是，permutation/3不是尾递归的，并且交换两个目标通常会大幅增加运行时间。它也很优雅，看起来很好，只涉及纯代码。请注意，OP要求略有不同：问题是子序列的排列，不一定包括整个列表。看看@repeat的简短、优雅和纯净的解决方案！ - mat

0

提示：如果您编写了一个谓词inselt(X,Y,Z)，它表示将Y插入到X中得到Z，那么这很容易实现。

inselt([E|X], Y, [E|Z]) :- inselt(X,Y,Z).
inselt(X, Y, [Y|X]).

然后，使用inselt/3可以递归编写comb/3。

- Charles Stewart

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hardmath · Accepted Answer

您所需要的涉及到一个列表的组合（选择子集）和排列（重新排列顺序）。

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

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