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

Question

我已经找到了用序言编写的幼稚排序的示例，并且我试图理解它:

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函数调用中检查所有排列？另外，如何修改烫发功能以写入所有排列？

Answer 1

这是，实际上是，是一种幼稚的排序-遍历所有可能排列的树，直到幸运地找到排序的树为止。我想那是O(n!)的复杂性:>

关于置换功能-它可以“向后”工作-请注意，该定义使头部脱离了结果。如果转过头去，您会注意到，与其删除它，实际上并没有通过向后工作来插入值，而是将其删除。由于算法在向后工作，因此选择的H ead可以是允许创建结果的任何内容，因此可以使用List中任何未使用的值。

基本上，置换算法可转换为以下过程实现:

从列表

中选择一个项目

将其放在Sorted

的前面

这样，您就可以生成排列。他们都是。

简而言之-彼尔姆通过从一个空解决方案开始并检查如何从有效删除中解决给定的解决方案来生成可能解决方案的整个空间。

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