Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: permutation - versions and their efficiency
Message-ID: <209@quintus.UUCP>
Date: 29 Jul 88 22:43:58 GMT
References: <1074@tuhold>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 106

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.