🚀 go-pugleaf

n <615@mannix.iros1.UUCP> Paul Tarau presented a version of
all_permutations/2, which gnerates a list of all permutations
of its first argument. He said it is 8 times faster than an
equivalent bagof/3-solution.

Here is a much faster and shorter all_permutations/2 version.
Actually it is even faster than getting all solutions of tail-
recursive perm/2 by backtracking!

all_perm(X,Y):-all_perm(X,[],[],Y).

all_perm([],L,R,[L|R]).
all_perm([X|L2],L,L3,R):-
	all_perm1(L2,L,[X],P2,R),
	all_perm(L2,[X|L],L3,P2).
	
all_perm1([],L,L1,P2,P2).
all_perm1([X|L2],L,L1,L3,R):-
	append(L1,L2,L1L2),
	all_perm(L1L2,[X|L],L3,P2),
	all_perm1(L2,L,[X|L1],P2,R).
	
append([],L,L).
append([X|L1],L2,[X|L3]):-append(L1,L2,L3).

I got the code by starting from the tailrecursive version and
transforming it by introducing difference lists. Sorry for the
cryptic variable-names.

Thom Fruehwirth