random cover of a range

[bearophile]

Andrei Alexandrescu:
>Well I don't buy it. If you make a point, you need to be more precise than such hand-waving.<

You are of right, but I am not able to give you good math here.
(I have used that algorithm to extract all the possible uints, in few minutes and with less than 1GB of RAM. That, plus my experience with hashes, tells me that this algorithm is good enough. If you want I can also implement it agan and test it with a growing number of items, to see from the graph of the timings if it's indeed linear.)


Bill B.:
>.. the real gotcha is that he's using O(n) extra memory. 10% of n is still O(n) memory for shuffling the last 10% of the items.<

No, you are wrong, in real computers using 110% of the memory needed to store your n items is generally acceptable.


Andrei Alexandrescu:
>Your handwaving ain't much better than my memory. Hey, either somebody goes through the math over here or we can give up on the whole thing and use O(n) storage for the blessed thing.<

We can implement both, and we can look what's better in practical situations.

Bye,
bearophile