How to access list permutations in prolog?

Question

I want to access list permutation and pass it as argument to other functions.

This is the permutation code:

takeout(X,[X|R],R).  
takeout(X,[F|R],[F|S]) :-
   takeout(X,R,S),
   write(S).

perm([X|Y],Z) :-
   perm(Y,W),
   takeout(X,Z,W).  
perm([],[]).

Solution 1

To start with, let's redefine your predicates so they don't do any unnecessary I/O:

takeout(X,[X|R],R).  
takeout(X,[F |R],[F|S]) :- takeout(X,R,S).

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

Now you have what could be considered a "pure" permutation function:

?- perm([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [1, 3, 2] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.

So, suppose you have a max_heap function that takes a list of values and produces a tree. I'll let you worry about that, so let's just posit that it exists and is called max_heap/2 and let's further posit that you have a way to display this attractively called display_heap/1. To "take" the permutation and "send" it as a parameter to these functions, you're really saying in math-ese: suppose P is a permutation of X, let's make a max_heap with it and display it. Or, suppose P is a permutation of X, H is a max heap made from X, let's display H:

show_heaps(List) :- perm(List, P), max_heap(P, H), display_heap(H).

This says the same thing as my English sentence: suppose P is a permutation of the list, then H is a heap representation of it, then display it. Technically, display_heap/1 is still a predicate which could be true or false for a given heap. In practice, it will always be true, and if you run this you'll still have to hit ; repeatedly to say, give me another solution, unless you use a failure-driven loop or an extralogical predicate like findall/3 to cause all the solutions to be found.

Edit: Let's discuss failure-driven loops and findall/3. First let me add some new predicates, because I don't know exactly what you're doing, but it doesn't matter for our purposes.

double([X|Xs], [Y|Ys]) :- Y is X*2, double(Xs, Ys).
double([],[]).

showlist(Xs) :- print(Xs).

So now I have a predicate double/2 which doubles the values in the list and a predicate showlist/1 that prints the list on standard output. We can try it out like so:

?- perm([1,2,3], X), double(X, Y), showlist(Y).
[2,4,6]
X = [1, 2, 3],
Y = [2, 4, 6] ;
[4,2,6]
X = [2, 1, 3],
Y = [4, 2, 6] ;
[4,6,2]
X = [2, 3, 1],
Y = [4, 6, 2] ;
[2,6,4]
X = [1, 3, 2],
Y = [2, 6, 4] ;
[6,2,4]
X = [3, 1, 2],
Y = [6, 2, 4] ;
[6,4,2]
X = [3, 2, 1],
Y = [6, 4, 2] ;
false.

When you type ; you're saying, "or?" to Prolog. In other words, you're saying "what else?" You're telling Prolog, in effect, this isn't the answer I want, try and find me another answer I like better. You can formalize this process with a failure-driven loop:

?- perm([1,2,3], X), double(X, Y), showlist(Y), fail.
[2,4,6][4,2,6][4,6,2][2,6,4][6,2,4][6,4,2]
false.

So now you see the output from each permutation having gone through double/2 there, and then Prolog reported false. That's what one means by something like this:

show_all_heaps(List) :- perm(List, X), double(X, Y), showlist(Y), nl, fail.
show_all_heaps(_).

Look at how that works:

?- show_all_heaps([1,2,3]).
[2,4,6]
[4,2,6]
[4,6,2]
[2,6,4]
[6,2,4]
[6,4,2]
true.

The other option is using findall/3, which looks more like this:

?- findall(Y, (perm([1,2,3], X), double(X, Y)), Ys).
Ys = [[2, 4, 6], [4, 2, 6], [4, 6, 2], [2, 6, 4], [6, 2, 4], [6, 4, 2]].

Using this to solve your problem is probably beyond the scope of whatever homework it is you're working on though.

Solution 2

We can define list_permutation/2 based on same_length/2 and select/3 like this:

:- use_module(library(lists),[same_length/2,select/3]).

list_permutation(As,Bs) :-
   same_length(As,Bs),          % redundant goal helps termination
   list_permutation_(As,Bs).

list_permutation_([],[]).
list_permutation_([A|As],Bs0) :-
    select(A,Bs0,Bs),
    list_permutation_(As,Bs).

Thanks to same_length/2, both of the following queries^1,2 terminate universally:

?- list_permutation([1,2,3],Ys).
  Ys = [1,2,3]
; Ys = [1,3,2]
; Ys = [2,1,3]
; Ys = [3,1,2]
; Ys = [2,3,1]
; Ys = [3,2,1]
; false.

?- list_permutation(Xs,[1,2,3]).
  Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

So far, so good. But what does the answer sequence look like if there are duplicate list items?

?- list_permutation([1,1,1],Ys).
  Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; false.

5/6 answers are redundant! What can we do? We simply use selectd/3 instead of select/3!

list_permuted(As,Bs) :-
   same_length(As,Bs),
   list_permuted_(As,Bs).

list_permuted_([],[]).
list_permuted_([A|As],Bs0) :-
   selectd(A,Bs0,Bs),           % use selectd/3, not select/3
   list_permuted_(As,Bs).

Let's re-run above query that gave us 5 redundant solutions before!

?- list_permuted([1,1,1],Ys).
  Ys = [1,1,1]
; false.

?- list_permuted(Xs,[1,1,1]).
  Xs = [1,1,1]
; false.

Better! All redundant answers are gone.

Let's compare the solution set for some sample case:

?- _Xs = [1,2,1,1,2,1,1,2,1],
   setof(Ys,list_permutation(_Xs,Ys),Yss),
   setof(Ys,list_permuted(_Xs,Ys),Yss),
   length(Yss,N).
N = 84, Yss = [[1,1,1,1,1,1,2,2,2],[1,1,1,1,1,2,1,2,2],[...|...]|...].

OK! How about empirical runtime measurements with a problem of a slightly bigger size?
We use call_time/2 for measuring the runtime in milli-seconds T_ms.

?- call_time(\+ (list_permutation([1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 8110.

?- call_time(\+ (list_permuted(   [1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 140.

OK! And with proper compilation of if_/3 and (=)/3, list_permuted/2 is even faster!

---

^{Footnote 1: Using SICStus Prolog version 4.3.2 (x86_64-linux-glibc2.12).
Footnote 2: The answers given by the Prolog toplevel have been post-processed for the sake of readability.}

Solution 3

If you just want to explore the permutations without the "False" in the end, this code might be helpful

takeout(X,[F |R],[F|S]) :- F\=X, takeout(X,R,S).
takeout(X,[X|R],R).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

So, the output of perm([a,b],B) would be

B=[a,b]
B=[b,a]

Comments

[BeginnerProgrammer]

i didn't understand your mean "unless you use a failure-driven loop or an extralogical predicate like findall/3 to cause all the solutions to be found."???????

[Daniel Lyons]

I added some explanation of that to my answer.