Prolog:如何编写(和使用)一个列出所有列表排列的函数? [英] Prolog: how to write (and use) a function that lists all list permutations?

问题描述

我发现了一个用 prolog 编写的简单排序的例子，我正在尝试理解它:

I've found such an example of naive sort written in prolog and I am trying to understand it:

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 函数来编写所有排列?

Naive_sort call works correctly but I just can't figure out why. The main problem is the permutation. When it is called implicitly it always returns only one value. How is it then possible that in naive_sort function call all permutations are checked? Also how could I modify perm function to write all permutations?

推荐答案

这真正是一种朴素的排序——它遍历所有可能排列的树，直到幸运地找到一个已排序的排列.我认为这具有 O(n!) 的复杂性:>

This is truly a naive sort -- it traverses the tree of all possible permutations until it luckily finds a sorted one. That's have a complexity of O(n!) i presume :>

关于置换函数——它向后"工作——请注意，定义将头部从结果中取出.如果您改变观点，您会注意到它实际上是通过向后工作来插入值而不是删除它.由于算法向后工作，因此选择的 Head 可能是允许创建结果的任何东西，因此列表中的任何未使用的值.

About the permutation function -- it works "backwards" -- note that the definition takes the head out of the result. If you turn around your point of view, you'll notice that instead of deleting it actually inserts values by working backwards. As the algorithm is working backwards, hence the Head chosen may be anything that will allow a result to be created, hence any unused value from List.

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

Basically the permutation algorithm translates to the following procedural implementation:

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

通过这种方式您可以生成排列.所有这些.

This way you generate permutations. All of them.

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

In short - perm generates the whole space of possible solutions by starting out of an empty solution and checking how the given solution is possible from a valid delete.

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

这篇关于Prolog:如何编写(和使用)一个列出所有列表排列的函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！