[comp.lang.prolog] small prolog problem

bend%fez@Sun.COM (George Bender) (05/18/88)

Hi,

I need a small prolog problem written to be inserted into
a larger module.  What this small program does is give all
of the permutaions of a list of three symbols.
Such as:
	called as: | ?- permu([a,b,c],X).

	solution:       X = [a,b,c];	
			X = [a,c,b];
			X = [b,a,c];
			X = [b,c,a];
			X = [c,a,b];
			X = [c,b,a];
			No.


Any suggestions?

Brian.

bruno@ecrcvax.UUCP (Bruno Poterie) (05/20/88)

a straightforward solution, but probably not the optimal one, is:

permute_list( [], []).
permute_list( InitList, [NewFirst|NewRest]) :-
	choose_first( InitList, NewFirst, InitRest),
	permute_list( InitRest, NewRest).

choose_first( [First|Rest], First, Rest).
choose_first( [First|Rest1], Elem, [First|Rest2]) :-
	choose_first( Rest1, Elem, Rest2).

lindsay@comp.vuw.ac.nz (Lindsay Groves) (05/23/88)

In article <53640@sun.uucp> bend%fez@Sun.COM (George Bender) writes:
>I need a small prolog problem written to be inserted into
>a larger module.  What this small program does is give all
>of the permutaions of a list of three symbols.

If you are ABSOLUTELY SURE that this will always only have to deal with lists
of three symbols, the best solution must be:
	permu([A,B,C], [A,B,C]).
	permu([A,B,C], [A,C,B]).
	permu([A,B,C], [B,A,C]).
	permu([A,B,C], [B,C,A]).
	permu([A,B,C], [C,A,B]).
	permu([A,B,C], [C,B,A]).
This is as efficient as you can get, and as intelligible.  It is perfectly
declarative and is reversible.

Whether you regard it is the obvious solution depends on how you think.  Most
of us have been trained to always look for general solutions (i.e. solutions
to more general problems) -- partly because it is usually more elegant than
brute force approaches such as the above, and partly to preempt program
changes if the problem is likely to be modified, as so often happens (hence
my emphasis above on ABSOLUTELY SURE).  There is usually a trade-off between
elegance/modifiablity and efficiency.  If you KNOW you have a special case
and it can be solved more efficiently than the general case, it is sensible
to make use of the additional information.  

Of course, with this problem, it is not going to make a significant 
difference, but the principle is worth remembering.

-- 

	Lindsay Groves

	Logic programmers' theme song: "The first cut is the deepest"