On Monday, 1 May 2017 at 08:44:25 UTC, Ola Fosheim Grøstad wrote:
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).
Keep also in mind that you can split the original array in two,
so it might be sufficient to have the permutations for various
2^M sizes if those are easier to generate (my guess, maybe
through some xor magic?)
E.g. if N = 21 then it can be split into 16 + (4 + 1)
So you can draw like this:
1. randomly select group_16 over group_5 based with 16/21
probability)
2. if group_5 selected: ramdomly select group_4 over group 1 on
4/5 probability
etc.
That way you only need log(N) permutation sequences to keep track
of. Which for all practical purposes are going to stay pretty low
(<20?)
Right?
