Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: Random permutation algorithm
Message-ID: <303@quintus.UUCP>
Date: 22 Aug 88 22:00:23 GMT
References: <5200012@m.cs.uiuc.edu> <32265@cca.CCA.COM> <532@aiva.ed.ac.uk>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 21

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.