[OT] Algorithm question

[H. S. Teoh via Digitalmars-d]

On Thu, May 04, 2017 at 01:19:43PM +0000, MysticZach via Digitalmars-d wrote:
[...]
> Maybe there's no way to deterministically jump to every element of an
> array with equal probability of hitting any given element satisfying a
> given predicate first. It sure would be cool if there were.

Of course there is.  The random permutation approach works. In this
case, the data itself is not allowed to be permuted, but equivalent
semantics can be obtained by permuting an array of indices into the
data. But the challenge is how efficiently you can generate a random
permutation so that the cost of generating one doesn't outweigh the O(n)
linear scan algorithm.

I'm surprised there are no (known) incremental algorithms for generating
a random permutation of 0..n that requires less than O(n) space.


T

-- 
Life is complex. It consists of real and imaginary parts. -- YHL