🚀 go-pugleaf

In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

>As noted in Bentley's December 1987 column, an alternative to Floyd's
>algorithm is to initialize an array a[1..N] to a[i]=i and then scan
>along from a[1] to a[M], exchanging each such a[i] with a randomly
>selected a[j] for j >= i.
>
>For N = M (Woo's question) this method is the one Jim Roth gave.  It is
>preferable to Floyd's method because it does not entail testing for
>previous occurrences.
>
>But for N >> M it has two drawbacks: the time to initialize the array,
>and the space required for it, both being O(N).  In contrast Floyd's
>method requires space O(M) and time somewhere between O(M) and O(M^2)
>depending on the method used to test for repetitions.  (For N some
>modest multiple of M one might instead keep track of repetitions using
>an array of N bits, i.e. N/8 bytes, initialized to 0.)

This method also can be implemented in O(M) space and O(M logM) time.

The general idea is that there is no need to initialize and maintain
the whole array. Only M entries can be changed, so for other entries
A[i] = i. Use any balanced search tree for storing needed information.
For details see: Chrobak, Harter, A note on random sampling, Information
Processing Letters 29 (1988) 255-256.

Marek

-- 
------------------------------------------------------------------
Marek Chrobak                              email: marek@cs.ucr.edu
Department of Computer Science             phone: (714) 787-3769
University of California, Riverside        fax  : (714) 787-4643