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?

score 10 · Answer 1 · answered Feb 04 '10 at 01:13

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:

The empty list is a permutation of itself.
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.

i knew all that except of the backtracking if anything fails - this explains a lot — agnieszka, Feb 04 '10 at 01:17
Describing it is so much easier if english is one's native language -_- — Kornel Kisielewicz, Feb 04 '10 at 01:19
I take that as a compliment, because it is not my native language either :-) — meriton, Feb 04 '10 at 01:26

Kornel Kisielewicz · Accepted Answer · 2010-02-04T01:03:23.820

9

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:

pick an item from List
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

edited Feb 04 '10 at 01:03

answered Feb 04 '10 at 00:50

Kornel Kisielewicz

55,802
15
111
149

so why whe calling this function it does display only ONE result, not all of them? – agnieszka Feb 04 '10 at 00:55
@agnieszka - it's not a function! It's a **predicate** that is true ONLY if the first argument is a permutation of the second. – Kornel Kisielewicz Feb 04 '10 at 00:59
@agnieszka - using GNU Prolog or SWI? – Kornel Kisielewicz Feb 04 '10 at 01:01
YESSS I know that, still you've written "it generates permutations. all of them." - it does not. it finds first combination of the unknown arguments that satisfies the predicate - so only ONE permutation. so how, how is it possible that it works when calling naive_sort? – agnieszka Feb 04 '10 at 01:02
@agnieszka -- because it keeps "calling" perm, until either is_sorted is true or it fails. – Kornel Kisielewicz Feb 04 '10 at 01:04
1. but when i call perm many times i always get the same result. 2. according to your edit: my result is different after that call - it displays only one result and i don't know how to modify it to display them all – agnieszka Feb 04 '10 at 01:06
tylko ze wielokrotne wywolywanie perm zawsze daje te same wyniki – agnieszka Feb 04 '10 at 01:07
@agnieszka - bo wielokrotnie wywołujesz, a nie ściągasz kolejne wyniki :). Wpisz średnik i enter po pierwszym wyniku -- będziesz miała szukanie dalszych rozwiązań -- http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/1.html – Kornel Kisielewicz Feb 04 '10 at 01:09
z nieba mi spadles dzien przed egzaminem... :D czyli po prostu prolog wie ze rozwiazan perm-a wyolaniu naive_sort jest wiele i skoro jedno nie dziala to probuje drugie. 2 dni na nauczenie prologa to jednak troche za malo - wielkie dzieki! ;) – agnieszka Feb 04 '10 at 01:12
Prolog wie, że póki perm mu nie powie "No", to może próbować czerpać z niego rozwiązania. 2 dni to zdecydowanie za mało, bo prolog to inny paradygmat programowania (programowanie logiczne) który znacząco różni się od szeroko znanych... powowdzenia! – Kornel Kisielewicz Feb 04 '10 at 01:18
:D Łojczysty język na stacku. no patrzcie... :D – naugtur May 20 '10 at 20:43
@naugtur, zbliżający się egzamin zmusza do radykalnych rozwiązań ;> – Kornel Kisielewicz May 20 '10 at 21:05

score 1 · Answer 3 · edited Mar 16 '15 at 15:22

1

use a semicolon (;) at the end of each permutation prolog would give you until there is no other permutation, prolog should say No

edited Mar 16 '15 at 15:22

dvhh

4,724
27
33

answered Mar 16 '15 at 14:46

cenyo

11
1

Yes, The reason why OP is seeing only one solution when called is probably because they aren't typing a ; to the ? prompt to see the others (forces it to fail and backtrack to find another solution). – David M W Powers Jun 19 '17 at 01:51

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

3 Answers3

Linked