Path: utzoo!attcan!uunet!husc6!bloom-beacon!mcgill-vision!odyssee!zap!iros1!ouareau!tarau
From: tarau@ouareau.iro.umontreal.ca (Paul Tarau)
Newsgroups: comp.lang.prolog
Subject: Re: Elegance=efficiency, the continuing story.
Summary: efficient 'all-permutations' in pure Prolog
Message-ID: <615@mannix.iros1.UUCP>
Date: 6 Aug 88 20:04:53 GMT
References: <214@quintus.UUCP>
Sender: news@iros1.UUCP
Reply-To: tarau@iros1.UUCP (Paul Tarau)
Organization: Universite de Montreal
Lines: 43

The following is an 'all_permutation' deterministic Horn clause
program I wrote some time ago, when trying (without full success)
to automatically convert nondeterministic programs to their
deterministic all-solutions counterparts.

all_permutations([],[[]]).
all_permutations([X|Xs],Perms2):-
	all_permutations(Xs,Perms1),
	extend_permutations(Perms1,X,[],Perms2).

extend_permutations([],_,Perms,Perms).
extend_permutations([Perm|Perms],X,Perms1,[[X|Perm]|Perms3]):-
	insert_item(Perm,X,[],Perms2,Perms3),
	extend_permutations(Perms,X,Perms1,Perms2).

insert_item([],_,_,Perms,Perms).
insert_item([Y|Ys],X,Acc,Perms1,[Zs|Perms2]):-
        reverse_and_append(Acc,[Y,X|Ys],Zs),
	insert_item(Ys,X,[Y|Acc],Perms1,Perms2).

reverse_and_append([],Acc,Acc).
reverse_and_append([X|Xs],Acc,Zs):-
	reverse_and_append(Xs,[X|Acc],Zs).

The practical interest of this kind of (very space-consuming) programs
is to be able to compare alternative solutions within a pure Prolog
framework. We can actually reduce the size of the generated list by
inserting some form of filtering at each inductive step.

The program uses the same kind of 'natural' induction on the first
argument as Richard O'Keefe's 'permute'.

It is about 8 times faster then an equivalent 'bagof' solution
(on a SUN-3,Quintus 2.2 with a list of 7 elements).

However, I think it is not as fast as it could be. For example
it might be a better way to extend permutations of the previous
inductive step then the use of 'append_and_reverse'.

Does someone know about a faster and/or shorter 'all_permutations'
program?

Paul Tarau