🚀 go-pugleaf

In article <24824@galaxy.ucr.edu> marek@wigry.ucr.edu (marek chrobak) writes:
>In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>>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.

Quite right, I'd entirely forgotten that option was available.  It
dates back at least to the 70's though it would take me a while to dig
up an instance.

This rather undermines the rationale Bentley offered for Floyd's
algorithm, at least for permutations, where I don't right now see any
big advantage of either algorithm over the other.  Simulating A[i]=i
with any prescribed amount of time and storage is essentially identical
in difficulty to inserting a default output ahead of K in Floyd's
algorithm under the same prescription.

The interest in Floyd's algorithm (besides its ingenuity) therefore
would seem to be its greater applicability, namely to the problem of
sampling combinations.  Here the storage requirement is only N bits,
which for N < M log_2 M would seem close to unbeatable.
-- 
Vaughan Pratt				There's safety in certain numbers.