[OT] Algorithm question

Ola Fosheim Grøstad via Digitalmars-d digitalmars-d at puremagic.com
Mon May 1 04:08:56 PDT 2017


On Monday, 1 May 2017 at 10:51:46 UTC, Ola Fosheim Grøstad wrote:
> 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?


But if you don't use a hardware random generator and are happy 
with more sloppy pseudo-randomness then you would be better of 
ditching the whole concept of permutations and replace it with 
some cylic random generators intead using the same technique I 
just outlined.

E.g. find a set of cyclic random generators and break down N into 
a sum of these cycle-sizes, then just keep track of the seed for 
each. If they are 2^N then you could use xor to get more 
randomness between runs.

Also in the algorithms above you need to change the probabilities 
each time you take away one index from a group (you don't want to 
draw from an empty group).



More information about the Digitalmars-d mailing list