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"