ok@quintus (07/20/88)
I saw (never mind where) the following definition today:
/*1*/ permute(X, [A|Z]) :-
select(A, X, Y),
permute(Y, Z).
permute([], []).
where select/3 is the usual
select(Item, [Item|Set], Set).
select(Item, [OtherItem|Set0], [OtherItem|Set]) :-
select(Item, Set0, Set).
This version of permute/2 looked ugly to me.
(1) From Clocksin & Mellish 1st edition I learned to put base cases
_first_. It is _much_ the clearest place to put them.
(2) It isn't obvious from the code that the induction is really on
the *first* argument of permute/2: if the first argument is unbound
permute/2 may fail to terminate even if the second argument is ground.
A version which has neither of these defects is
/*2*/ permute([], []). % to permute [], return []
permute([X|Xs], Ys1) :- % to permute [X|Xs],
permute(Xs, Ys), % permute Xs giving Ys
select(X, Ys1, Ys). % insert X anywhere in Ys giving Ys1
Now, I think this version is much easier to read.
The reason for the title of this message is that it turns out to be
considerably faster in Quintus Prolog: 4 times faster for tiny lists,
5 times faster for 10 element lists. I can explain the result after
the event, but I wasn't expecting anywhere near that big a difference.
Elegance pays!
Of course, that version still suffers from the well known problem that
it can't be used to solve for the first argument given the second.
But at least it is a bit less surprising that that is so. In fact we
can easily fix that bug and produce a satisfactory permute/2:
/*2*/ permute(Xs, Ys) :-
permute(Xs, Ys, Ys).
permute([], [], []).
permute([X|Xs], Ys1, [_|Zs]) :-
permute(Xs, Ys, Zs),
select(X, Ys1, Ys).
This is a bit less than twice as slow as version /*2*/, but it is
more than twice as fast as version /*1*/ and works both ways around.
[permute(Xs, Ys, Zs) checks that Xs and Zs are the same length, so
that if Ys is known, it will terminate.]tarau@ouareau.iro.umontreal.ca (Paul Tarau) (08/07/88)
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