[OT] Algorithm question

[Ola Fosheim Grøstad via Digitalmars-d]

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?