On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote:
Is there an algorithm for *incrementally* generating a random
permutation of indices?
Does it exist? Yes, because you can build permutation tables for
it, but you'll have to find the closed form for it that is
efficient... Can you do that without selecting a specific N? It
is easy for N=2 and N=3 at least.
E.g.
For array length 2 you get the 2 permutations: 0 1, 1 0
Then you just select one of them at random (you know the number
of permutations)
So if it exists you'll should probably do a search for
permutations. "How do I efficiently generate permutation number N"
Of course for smaller N you could generate a big array of bytes
and compress it by having arrays of slices into it (as many
permutations will share index sequences).
