Prolog: how to write (and use) a function that lists all list permutations?

Question

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

Answer 1

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

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. pick an item from List
2. put it into front of Sorted

This way you generate permutations. All of them.

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

Answer 2

The main problem is the permutation function. When it is called implicitly it always retrns only one value.

Prolog is a language that always attempts on proving the truth of a statement, by deriving it using the axioms (facts or rules) given.

perm is not a function in the sense of procedural programming. perm is a predicate, about which we tell prolog two things:

1. The empty list is a permutation of itself.
2. List is a permutation of [H|Perm] if there is a list Rest such that Rest is obtained by deleting H from List, and Rest is a permutation of Perm.

When asked whether some list is a permutation of another, prolog will attempt to apply these derivation steps (recursively) to prove it. If this recursion reaches a dead end, i.e. a statement which can not be proven as no rules can be applied to it, it backtracks.