Search code examples
listprologpermutationprolog-dif

How to access list permutations in prolog?


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

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