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

Question

I found such an example of naive sorting written in the prolog, and I'm trying to figure it out:

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). 

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

Answer 1

This is truly a naive variety - it traverses the tree of all possible permutations until, fortunately, it finds a sorted one. It has complexity O (n!), I suppose:>

About the permutation function - it works "backward" - note that the definition takes the head out of the result . If you expand your point of view, you will notice that instead of deleting it, it inserts values, turning back. Since the algorithm works in the opposite direction, therefore, the selected H ead can be anything that allows you to create a result, therefore, any unused value from the list.

Basically, the permutation algorithm is transferred to the following procedural implementation:

• select an item from the list
• put it before sorting

This way you create permutations. All of them.

In short-perm, it generates the entire space of possible solutions, starting with an empty solution and checking how this solution is possible from a valid deletion.

 ?- 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 implicit, it always gives only one value.

A prologue is a language that always tries to prove the truth of a statement by deriving it using the axioms given (facts or rules).

perm not a function in the sense of procedural programming. perm is a predicate that we are talking about a prolog about two things:

• An empty list is a rearrangement of oneself.
• List is a permutation [H|Perm] if there exists a Rest list such that Rest obtained by removing H from List , and Rest is a perm permutation.

When asked if a list is a permutation of another, the prolog will attempt to apply these derivation steps (recursively) to prove it. If this recursion reaches a dead end, i.e. An assertion that cannot be proved, since no rules can be applied to it, it goes back.

Answer 3

using a semicolon (;) at the end of each permutation proposition will give you as long as there is no other permutation, the prolog should say "No"