[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