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 可能是任何允许创建结果的东西，因此是 List 中任何未使用的值.

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. 放在 Sorted 前面

这样您就可以生成排列.全部.

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屋！