Path: utzoo!attcan!uunet!mcvax!tuvie!tuhold!thom
From: thom@tuhold (Thom Fruehwirth)
Newsgroups: comp.lang.prolog
Subject: permutation - versions and their efficiency
Message-ID: <1074@tuhold>
Date: 27 Jul 88 14:42:10 GMT
Organization: Institut f. Angewandte Informatik, TU Vienna
Lines: 66


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