Prolog random permutation

Permuting a given list comes up as a subroutine of the REVERSE game. I’ve seen a pretty crazy implementation of shuffle which involves extracting a random element from the source list and putting it in the result. Pretty heavy on the Prolog engine. I think I got a slightly better one: iterate the given list, appending or prepending each element to the initially empty result, with a probability of 50%. Same shit.

permute([H|T], [H|R]) :-
random(X), X < 0.5, !,
permute(T, R).
permute([H|T], R) :-
permute(T, Q),
append(Q, [H], R).
permute([], []).

If append isn’t fast enough, you can always go crazy with difference lists.

The second cut is meant to avoid an extra unneeded unification attempt with the third predicate. Things work just as well without it.

GNU Prolog doesn’t seem to have a very good random number generator, so I gave it some slack:

permute_on_steroids(L, R) :-
permute(L, P),
permute(P, Q),
permute(Q, R).

Leave a Reply