CODEWITHSUNDEEP
listprologpermutation
Christian Baker
Christian Baker

Reputation: 389

Prolog - How does this permute function work?

For the life of me I can't figure out how exactly this permute function works. 

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

It looks to me like the first append takes the last element of L and unifies it with H. Then the inner perm call permutes the other elements and unifies them with T. I'm just not sure what the second append function does. I know that without it, every attempt to find a new solution reduces the list size by 1, but I can't explain this behavior.

Upvotes: 1

Views: 700

Answers (1)

Fred Foo
Fred Foo

Reputation: 363737

It looks to me like the first append takes the last element of L and unifies it with H.

Not the last element; some element.

append(V, [H|U], L) can be read L = V + [H] + U, for some lists V and U, and some element H. It breaks L into a part before H and a part after H, after picking an element H:

?- append(V, [H|U], [1,2,3]).
V = [],
H = 1,
U = [2, 3] ;
V = [1],
H = 2,
U = [3] ;
V = [1, 2],
H = 3,
U = [] ;
false.

The next append can then be read W = V + U, so W is L but with some element H removed.

(SWI-Prolog has a select predicate that does the same thing in a more readable way:

perm(L, [H|T]) :-
    select(H, L, Rest),
    perm(Rest, T).
perm([], []).

But it also has a permutation predicate, so why bother ;)

Upvotes: 2

Related Questions