thom@tuhold (Thom Fruehwirth) (07/27/88)
In PROLOG Digest Vol 6 Issue 52 of Fri, 22 july 88 Richard O'Keefe comments on different versions of permute/2 and their efficiency. I played around with permutations some time ago and ended up with a dozen of versions. In the following I refer to the three versions of permute/2 given by Richard as /*1*/,/*2*/,/*3*/. I made some measurments using a Prolog running on a Macintosh. (I dont mention the name of the Prolog here, it is full of bugs) If the fastest version /*2*/ takes unit time, /*3*/ takes 1.5 and /*1*/ 5 times longer. Version /*3*/ is preferable in all aspects, e.g. it can never go into an infinite loop by itself and works with all combinations of bindings. Still, there is another slightly more intuitive version equivalent to /*3*/ in behaviour and timing: /*4*/ permute4(L1,L2) :- same_length(L1,L2), permute2(L1,L2). /* permute2/2 as version /*2*/ */ same_length([],[]). same_length([_|L1],[_|L2]) :- same_length(L1,L2). Interestingly both /*3*/ and /*4*/ are about 10 percent slower when called with the first argument free and the second bound. The time to generate all permutations is always proportional to O(n!) where n is the number of elements in the list to permute. Using impure Prolog, namely var/1 and cut, we get the speed of /*2*/ with ugly version /*5*/: /*5*/ permute5([],[]). permute5([X|Xs],Ys1) :- var(Ys1), !, Ys1=[Y|Ys], permute5(Xs,Ys), select(X,Ys1,Ys). permute5(Ys1,[X|Xs]) :- Ys1=[Y|Ys], permute5(Xs,Ys), select(X,Ys1,Ys). /* select/3 see Richard */ Note that the explicit unification with =/2 is necessary to guarantee termination in all cases. Once the second clause has been used in the recursion, the third clause will never be used in subsequent recursions, as the second argument is always a new variable Ys. Last, let me suggest a problem: Is it possible to write a predicate permute/2 (calling permute/n) equivalent to standard permutation (version /*2*/) without using select/3 ? Of course I dont mean just wrapping normal permute/2 and select/3 with permute/n. I mean something like: /*6*/ permute(L1,L2) :- permute(L1,L2,...). /* Code of permute/n and nothing else */ I will comment on the problem in a later posting. thom fruehwirth, vienna
ok@quintus.uucp (Richard A. O'Keefe) (07/30/88)
In article <1074@tuhold> thom@tuhold (Thom Fruehwirth) writes: >In PROLOG Digest Vol 6 Issue 52 of Fri, 22 july 88 >Richard O'Keefe comments on different versions of permute/2 >and their efficiency. >Still, there is another slightly more >intuitive version equivalent to /*3*/ in behaviour and timing: > >/*4*/ permute4(L1,L2) :- > same_length(L1,L2), > permute2(L1,L2). > >/* permute2/2 as version /*2*/ */ > > same_length([],[]). > same_length([_|L1],[_|L2]) :- same_length(L1,L2). > This is what the Quintus Prolog library predicate permutation/2 used to do. It's a neat hack which I learned from Ed Stabler. The version I recommended in V6I52 has replaced it, being faster. But the two are very close: each step of version /*3*/ does one step of version /*2*/ and one step of same_length. >Last, let me suggest a problem: >Is it possible to write a predicate permute/2 (calling permute/n) >equivalent to standard permutation (version /*2*/) without using >select/3? Of course I dont mean just wrapping normal permute/2 >and select/3 with permute/n. I mean something like: >/*6*/ permute(L1,L2) :- permute(L1,L2,...). >/* Code of permute/n and nothing else */ I don't know whether this is what Fruehwirth had in mind, but it seems to meet his conditions. perm([], []). perm([H|T], [X|P]) :- perm(T, H, Q, Q, X, P). perm(T, H, T, [], H, []). perm(T, H, T, [G|L], H, [X|P]) :- perm(L, G, Q, Q, X, P). perm([H|T], G, [G|L], Q, X, P) :- perm(T, H, L, Q, X, P). This rather confusing piece of code was obtained by starting with perm([], []). perm([H|T], [X|P]) :- select(X, [H|T], Q), perm(Q, P). then introducing a new predicate perm(T, H, L, Q, X, P) :- select(X, [H|T], L), perm(Q, P). This gives us perm([], []). perm([H|T], [X|P]) :- perm(T, H, Q, Q, X, P). as the definition of perm/2. I then unfolded select(X, [X|L], L). select(X, [H|T], [H|L]) :- select(X, T, L). in perm/6, getting the clauses perm(T, H, T, Q, H, P) :- perm(Q, P). perm(T, H, [H|L1], Q, X, P) :- select(X, T, L1), perm(Q, P). Since select(_, L, _) can only succeed when L is a cons cell, we can make that explicit, and write the second clause as perm([H1|T1], H, [H|L1], Q, X, P) :- select(X, [H1|T1], L1), perm(Q, P). But the body of this is just perm/6 all over again, so folding gives us perm(T, H, T, Q, H, P) :- perm(Q, P). perm([H|T], G, [G|L], Q, X, P) :- perm(T, H, L, Q, X, P). We're still not quite there. The last step is to unfold perm/2 in the first clause. We get two cases: perm(T, H, T, [], H, []). perm(T, H, T, [H1|T1], H, [X|P]) :- perm(T1, H1, Q, Q, X, P). The final result was shown above. We could even add another argument to it (using the original P as a counter) to make it work both ways around. I don't think it's particularly useful to have permutation done with only one recursive predicate, but I think the derivation of the result may be of interest.