[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