Prolog:如何编写(和使用)列出所有列表排列的函数？

Question

我发现了这样一个用prolog写的天真排序的例子,我试图理解它:

naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).

is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]):-X=<Y,is_sorted([Y|T]).


perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).

delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).

Naive_sort调用正常,但我无法弄清楚原因.主要问题是排列.当隐式调用它时,它总是只返回一个值.那怎么可能在naive_sort函数调用中检查所有排列？另外,我如何修改perm函数来编写所有排列？

Answer 1

主要问题是排列函数.当它被隐式调用时,它总是只返回一个值.

Prolog是一种总是试图证明陈述真实性的语言,通过使用给定的公理(事实或规则)来推导它.

perm在程序编程意义上不是一个功能.perm是一个谓词,我们告诉prolog两件事:

1. 空列表是其自身的排列.
2. List是的置换[H|Perm],如果有一个列表Rest,使得Rest通过删除得到的H从List,和Rest是的置换Perm.

当被问及某个列表是否是另一个列表的排列时,prolog将尝试应用这些派生步骤(递归地)来证明它.如果这个递归到达死胡同,即一个无法证明没有规则可以应用于它的语句,它就会回溯.

Answer 2

这真的是一种天真的类型 - 它遍历所有可能排列的树,直到幸运地找到一个排序的树.那是O(n!)的复杂性我认为:>

关于置换函数 - 它"向后"工作 - 请注意,该定义将结果排除在外.如果你转过你的观点,你会注意到,实际上不是删除它,而是通过向后工作来插入值.由于算法是向后工作的,因此所H选择的ead可以是允许创建结果的任何内容,因此来自List的任何未使用的值.

基本上,置换算法转换为以下程序实现:

1. 从列表中选择一个项目
2. 把它放在Sorted的前面

这样就可以生成排列.他们都是.

简而言之,perm通过从一个空的解决方案开始并检查有效删除中给定解决方案的可能性来生成可能解决方案的整个空间.

?-  perm( [ 1, 2, 3 ] , P ) 
P = [1, 2, 3]; 
P = [1, 3, 2]; 
P = [2, 1, 3]; 
P = [2, 3, 1]; 
P = [3, 1, 2]; 
P = [3, 2, 1]; 
no