# Algorithm for choosing 3 unique random numbers... with no looping or branching **URL:** \ **Category:** Factual Questions\ **Created:** [August 26, 2022, 6:03pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404 "2022-08-26T18:03:35Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Ponderoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ponderoid/32/19221_2.png) [@Ponderoid](https://boards.straightdope.com/u/Ponderoid)\ **Post date:** [August 26, 2022, 6:03pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/1 "2022-08-26T18:03:36Z")
I wrote some code that picks a random integer in the range 1-N, N is always at least 5. RandomInteger1 = floor(random(N))+1 The random function here returns floats from 0 up to but not including exactly N. Pretty standard in many languages. A new iteration of the program required me to pick a new random number that differed from the first result. I could have written a loop that kept rolling until it got something that differed, but just for fun, I avoided loops or branching this way: RandomInteger2 = (RandomInteger1 + floor(random(N-1))) mod N + 1 (did I type that right? I hope so) Now I discover I need a 3rd random number that differs from the first 2 results. Is there any fun trick to make my 3rd random pick unique without doing any branching or looping? Even more beyond 3 as long as N is big enough? ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [August 26, 2022, 6:48pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/2 "2022-08-26T18:48:23Z")
This may be “cheating,” but in some languages, it would be relatively easy to generate a list of the first N integers, shuffle that list, and then pick off the first three (or however many you need) numbers from that shuffled list. Another approach I was playing around with: In many languages, an expression that evaluates to TRUE has a numerical value of 1 (or -1). In that case, one alternative to your approach that seems to work for two random integers is to replace your RandomInteger2 = (RandomInteger1 + floor(random(N-1))) mod N + 1 with R = floor(random(N-1)) + 1 RandomInteger2 = R + (R \>= RandomInteger1). For example, suppose N is 10 and RandomInteger1 turns out to be 6. Then R will be a randomly chosen integer from 1 to 9. If R is 1, 2, 3, 4, or 5, that’s what RandomInteger2 will be, but if R is 6, 7, 8, or 9, RandomInteger will be R+1, giving you 7, 8, 9, or 10. Unfortunately, so far I have been unable to find a way to successfully adapt this method to more than two RandomIntegers, though it seems like there ought to be a way. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [August 26, 2022, 6:53pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/3 "2022-08-26T18:53:08Z")
Since I don’t want to explicitly give an answer to a nice homework question. Think about redoing the case of two numbers. First pick a number r between 0 and N-2. Then consider the pair (r, N-1) and randomly shift those around by a 2nd random number from 0 to N-1 mod N. Note to **Thudlow\_Boink** The OP said no looping. Can’t shuffle N numbers without a loop. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [August 26, 2022, 6:56pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/4 "2022-08-26T18:56:39Z")
> [@ftg](#): > > Note to **Thudlow\_Boink** The OP said no looping. Can’t shuffle N numbers without a loop. That’s one reason I said it might be “cheating.” Does it count if a built-in (or importable) function is doing the looping for you? ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [August 26, 2022, 7:06pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/5 "2022-08-26T19:06:41Z")
BTW: One very important sanity check to make in such problems is that the probabilities of the choices come out right. E.g., if the random choice products comes to N\*(N-1)\*(N-2) (or a multiple thereof) then you might have it. If the the products comes to N\*N\*N you don’t. ---
**Author:** ![Ponderoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ponderoid/32/19221_2.png) [@Ponderoid](https://boards.straightdope.com/u/Ponderoid)\ **Post date:** [August 26, 2022, 7:11pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/6 "2022-08-26T19:11:57Z")
> [@Thudlow\_Boink](#): > > That’s one reason I said it might be “cheating.” Does it count if a built-in (or importable) function is doing the looping for you? Yeah, I’d count that as cheating. I’d know the looping/branching is still happening, just abstracted away in the higher level code. If I end up needing a large number of random picks, randomizing a list probably will be the way to go, if only to guarantee the routine will finish in a reasonable finite time. This is just an amusing intellectual exercise right now. I’ve already got the 3-pick version working with a do-while loop. I was just wondering if there might be a clever hack somewhere. ---
**Author:** ![Ponderoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ponderoid/32/19221_2.png) [@Ponderoid](https://boards.straightdope.com/u/Ponderoid)\ **Post date:** [August 26, 2022, 7:51pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/7 "2022-08-26T19:51:15Z")
> [@ftg](#): > > First pick a number r between 0 and N-2. Then consider the pair (r, N-1) and randomly shift those around by a 2nd random number from 0 to N-1 mod N. That stumped me; I don’t see how you get 3 random picks from that? ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 26, 2022, 8:16pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/8 "2022-08-26T20:16:35Z")
> [@ftg](#): > > Can’t shuffle N numbers without a loop. Sure you can, at least as long as N is bounded. There are lots of tricks one can use here. For instance, to sort two numbers: sel = (Input1 \< Input2) Output1 = (sel \* Input1) + ((1 - sel) \* Input2) Output2 = (sel \* Input2) + ((1 - sel) \* Input1) Using that, you can sort a whole list if you want. As for the OP, use the same trick you came up with to generate an R3 that is not R1, or (R1-1). It might be R2, though, so add: R3 = R3 + (R2 == R3) I’m assuming that boolean operators return 0 or 1, which is generally the case for C-like languages. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 26, 2022, 8:46pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/9 "2022-08-26T20:46:39Z")
Shuffling 5 numbers in arr, no branches: ```auto fun swap(a, b): t = a a = b b = t swap(arr[4], arr[random_int(0, 4)]) swap(arr[3], arr[random_int(0, 3)]) swap(arr[2], arr[random_int(0, 2)]) swap(arr[1], arr[random_int(0, 1)]) ``` If N is bounded but unknown, one could pad the list out to the maximum number, but use conditional swaps for indices\ **Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 26, 2022, 9:20pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/10 "2022-08-26T21:20:26Z") You cannot make two or more uniform-probability draws from any set with no duplicates, without loops of unbounded possible length. All random number generators ultimately give you bits, which mean that with bounded loops, all your probabilities will be rational numbers with a denominator that’s a power of two. N and N-1 will never both be powers of two, so you can’t do what you’re asking for. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 26, 2022, 9:30pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/11 "2022-08-26T21:30:05Z")
You need one more requirement: that the program always produces a result. If you check for the bad range and divide by 0 in that case, the program will blow up and not produce a biased result. You can make the likelihood of his happening as low as desired, including lower than the odds that an asteroid will fall on your head at just that moment. (also, I was assuming that the ranged RNG function didn’t count as part of the “no looping” restriction) ---
**Author:** ![TroutMan](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/troutman/32/6721_2.png) [@TroutMan](https://boards.straightdope.com/u/TroutMan)\ **Post date:** [August 26, 2022, 9:54pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/12 "2022-08-26T21:54:09Z")
> [@Dr.Strangelove](#): > > As for the OP, use the same trick you came up with to generate an R3 that is not R1, or (R1-1). It might be R2, though, so add: > R3 = R3 + (R2 == R3) That raises a question - do the random numbers have to be equally distributed? Your technique could work, but R3 will equal R2+1 twice as often as it will be any other individual number. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 26, 2022, 10:04pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/13 "2022-08-26T22:04:31Z")
Oops! You’re correct, and I didn’t mean to do that. Actually I had it right when I was working it out earlier, then thought I simplified it properly, but clearly did not. Assuming R1 and R2 have been generated already, first sort them using my example code above. Then: R3 = (R2 + 1 + rand\_int(N-2)) mod N R3 = R3 + ((R3 \>= R1) && (R3 \< R2)) At least I think that’s right… might have screwed up some of the comparisons slightly. Basically, shift _everything_ in the R1-R2 range forward. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [August 26, 2022, 10:26pm UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/14 "2022-08-26T22:26:47Z")
I was assuming the OP was satisfied with an RNG that produced enough bits that doing mod would result in an acceptable distribution for small N like 3. (And it’s trivial to get a uniform distribution using N calls with mods to an RNG even without ifs.) [Ponderoid](https://boards.straightdope.com/u/Ponderoid) “That stumped me; I don’t see how you get 3 random picks from that?” You left out a key sentence. This is how you do two. Three is a very simple extension. ---
**Author:** ![Sam\_Stone](https://avatars.discourse-cdn.com/v4/letter/s/ecccb3/32.png) [@Sam\_Stone](https://boards.straightdope.com/u/Sam_Stone)\ **Post date:** [August 27, 2022, 1:04am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/15 "2022-08-27T01:04:50Z")
1. populate a set with random numbers. 2. read the first three. ---
**Author:** ![gnoitall](https://avatars.discourse-cdn.com/v4/letter/g/bb73d2/32.png) [@gnoitall](https://boards.straightdope.com/u/gnoitall)\ **Post date:** [August 27, 2022, 1:27am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/16 "2022-08-27T01:27:43Z")
> [@Sam\_Stone](#): > > populate a set with random numbers. Without a loop. I guess if you didn’t mind brute force, unroll the loop. Simply generate N random numbers by calling the RNG in N sequential (linear) calls. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 27, 2022, 1:31am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/17 "2022-08-27T01:31:08Z")
That doesn’t guarantee distinct numbers, though. If you’re taking that approach, you need to _permute_ a set of all numbers 0…N-1 and pick the first three. Which is also possible if N is known in advance. ---
**Author:** ![Sam\_Stone](https://avatars.discourse-cdn.com/v4/letter/s/ecccb3/32.png) [@Sam\_Stone](https://boards.straightdope.com/u/Sam_Stone)\ **Post date:** [August 27, 2022, 4:10am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/18 "2022-08-27T04:10:49Z")
A set doesn’ contain duplicates. As soon as there are three numbers in the set, they are unique, assuming your random number generator is decent. You do need to test for three members, though, and keep generating until you have them. You can do that without a loop, but it’d be clunky. Or you could just generate a few of them and trust that you have at least three that aren’t duplicate. The odds are very long that you wouldn’t get three unique random numbers of reasonable size out of, say ten generated numbers. Unless, again, the RNG is doing something stupid. Then throw an exception… ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 27, 2022, 4:34am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/19 "2022-08-27T04:34:17Z")
> [@Sam\_Stone](#): > > A set doesn’ contain duplicates That’s true for a mathematical set, but mathematical sets aren’t ordered–at least in your OP, you implied that they were with “read the first three.” Sets in programming languages tend to be implemented with hash tables, though there are some variations (like large bitfields) depending on the requirements. Most of these implementations themselves need branching. In fact, most require significant runtime infrastructure, like a memory allocator. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [August 27, 2022, 4:40am UTC](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404/20 "2022-08-27T04:40:55Z")
> [@ftg](#): > > And it’s trivial to get a uniform distribution using N calls with mods to an RNG even without ifs Is it? When I first read this statement, I agreed, but now I don’t think so. It doesn’t matter how many times you read the RNG; as long as the number is bounded, the denominator must be a power of 2 (as **Chronos** notes). That isn’t a common multiple of N and N-1 unless N=2. You can do it with a loop–which works because you might call the RNG an indefinite number of times, allowing you to construct whatever denominator you want. But N times just gives you a denominator of 2^{NB}, not N2^B or anything like that. [Next page](https://boards.straightdope.com/t/algorithm-for-choosing-3-unique-random-numbers-with-no-looping-or-branching/970404.md?page=2)