Prolog compute the permutation

Question

I'm writing a permutation function [a,b]-->[[[a], [b]], [[a, b]]

I have this so far, but it doesn't work.

perm([],[]).
perm(L,[H|T]) :- append(V,[H|U],L), append(V,U,W), perm(W,T).

score 5 · Accepted Answer · edited May 23 '17 at 11:44

Given your example, it looks like you might actually be wanting the powerset, not the permutation, of the given list.

For instance, the powerset of [a,b] is the set {[a,b], [a], [b], []}.

To compute the powerset of a list of items in Prolog, look at this answer by @gusbro. If this helps you, also please upvote that answer.

If you want all solutions of the powerset of a list L at once, you can wrap the call to powerset/2 in a findall/3 call like this:

?- findall(S, powerset(L, S), Ss).

If, on the other hand, you're after the partitions (as you've mentioned in one of your earlier edits), consider the following:

partition(L, PL) :-
    partition(L, [], PL).

partition([], [], []).
partition([X|Xs], As, R) :-
    % add X into the new partition... 
    append(As, [X], NewAs),  
    partition(Xs, NewAs, R).
partition(L, [A|As], [[A|As]|R]) :-
    % ...or, collect the current non-empty partition
    partition(L, [], R).

The predicate partition/2 takes a list and returns all partitions, as you've described. For example:

?- partition([a,b,c],L).
L = [[a, b, c]] ;
L = [[a, b], [c]] ;
L = [[a], [b, c]] ;
L = [[a], [b], [c]] ;
false.

`bagof/3` appears preferable to also treat variables nicely. — false, Oct 11 '12 at 18:27

score 3 · Answer 2 · answered Oct 10 '12 at 20:29

Really? It seems to work in SWI-Prolog:

?- [user].
|: perm([],[]).
|: perm(L,[H|T]) :- append(V,[H|U],L), append(V,U,W), perm(W,T).
|: % user://1 compiled 0.00 sec, 3 clauses
true.

?- perm([a,b,c], X).
X = [a, b, c] ;
X = [a, c, b] ;
X = [b, a, c] ;
X = [b, c, a] ;
X = [c, a, b] ;
X = [c, b, a] ;
false.

?- perm([a,b,c,d], X).
X = [a, b, c, d] ;
/* trimming 22 solutions */
X = [d, c, b, a] ;
false.

This also yields the number of answers you'd expect: 3! = 6, 4! = 24. What's not working for you?

score 1 · Answer 3 · answered Oct 10 '12 at 21:22

Quick note: Prolog doesn't offer functions, but relations.

In this case, perm/2 will hold true when the arguments are one the permutation of the other.

I find this definition more readable than your.

perm([], []).
perm([E|Es], P) :-
    perm(Es, Q),
    select(E, P, Q).

It's almost the same as that of permutation/2 SWI-Prolog, but hides a bug...

Prolog compute the permutation

3 Answers3