[OT] Algorithm question
MysticZach via Digitalmars-d
digitalmars-d at puremagic.com
Mon May 1 14:54:43 PDT 2017
On Monday, 1 May 2017 at 16:56:58 UTC, MysticZach wrote:
> The goal is to have the first hit be the one you return. The
> method: if a random pick doesn't satisfy, randomly choose the
> partition greater than or less than based on
> uniform(0..array.length-1), and do the same procedure on that
> partition, reusing the random index to avoid having to call
> uniform twice on each recursion (one to choose a partition and
> one to choose an index within that partition). If the
> probability of choosing a partition is precisely proportional
> to the number of elements in that partition, it seems to me
> that the result will be truly random, but I'm not sure.
Now I'm questioning this, because if the positive cases are
unevenly distributed, i.e., [111111000100], the last one has
about 50% chance to get picked instead of a 1 in 7 chance with my
method. I guess you'd need to build a whole new array like the
others are saying.
More information about the Digitalmars-d
mailing list