mardi 31 janvier 2017

How to generate 2 non-adjacent random numbers in a range

I need to generate 2 random numbers in a range [A..B] with the restriction that the numbers can not be adjacent. I would like to do it in constant time (I don't want to keep drawing until the 2nd value is good).

I can think of several ways to do this:

  • Pick the first, then pick one that fits after it: Draw V1 from the range [A..B-2], then draw V2 from the range [V1+2..B]
  • Pick the distance between them, then place them: Draw d from [2..B-A] and V1 from [0..B-A-d] then V2=V1+d
  • Pick the first, then pick an offset to the second one: Draw V1 from the whole range, then draw d from the range [A+2-V1..B-V1-1], and set V2= d<=0 ? V1-2+d : V1+1+d
  • Pick the first, then pick the distance to the second with wrapping: pick V1 from [A..B], d from [0..A-B-2], V2 = V1+d; V2 = V2>B ? V2-(B-A)

I want the most random method (generates most entropy, has most even distribution). I think the last 2 are equivalent and more random than the first two. Is there an even better way?




Aucun commentaire:

Enregistrer un commentaire