🚀 go-pugleaf

In article <532@aiva.ed.ac.uk> ken@uk.ac.ed.aiva (Ken Johnson,E32 SB x212E) writes:
>Story so far: Looking for a way of randomly permuting N elements
>in a declarative language.
>Here it is in Prolog. Untested etc. I am reasonably certain you could
>speed this up, but the question was to show that it could be done at all,
>and I've only got ten minutes...

This topic has already been discussed in comp.lang.prolog.
Results to date:
    if terms can have at most K elements,
    an O(N.log N) worst case time method exists.
              K
    if terms can have any number of elements (say >2N),
    an O(N) expected time method exists.

An O(N.lg N) method is available in the Quintus Prolog library.  It has
the structure of a sort, but instead of doing comparisons it generates
O(N.lg N) random bits.  [An N.log(K,N) method would be like a radix sort.]

Note that since there are N! permutations, a method of generating random
permutations must generate at least lg(N!) = O(N.lg N) random bits.