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?
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.
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.
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.
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.
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.
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<N.
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.
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)
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.
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.
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
“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.
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.
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…
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.
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.