all-permutations is faster than permutation 
Author Message
 all-permutations is faster than permutation


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



Sun, 17 Jan 1993 13:41:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. A permutation on permutations

2. Generating permutations

3. Finding permutations

4. All Permutations

5. All permutations

6. Permutation

7. Permutations

8. Linked list to Permutation vector

9. Permutations

10. Puzzler: function of permutation vector

11. Fwd: re: Puzzler: Permutations and Anagrams

12. Puzzler: Permutations and Anagrams

 

 
Powered by phpBB® Forum Software