thom@tuhold (Thom Fruehwirth) (08/23/88)
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