I want to generate a (pseudo) random sequence of numbers between 0 and N,
Each number should only appear once in the sequence and the order should be random.
I could just take an array of all the numbers and shuffle it, but I don’t want to instantiate the whole list at once.
Other things I’d like not to do:
Store a list of every number I’ve generated.
This seems like it’s a problem that someone will have solved before.
Any clues as to how I might do this?
(My initial guess was constructing a Linear congruential generator with a specific period, but I’m not sure if that is the right thing to be doing.
Can you say a bit more about your constraints? Why can’t you generate the
whole list at once, or store a list of elements already generated?
Fundamentally, I’m not sure this is possible without doing one of those
(though I would be happy to be proven wrong). Also, how big might N be?
In general it looks like this is non-trivial but doable. I think what you want to be Googling for is something like “permutation representation” or something, e.g. http://www.dcc.uchile.cl/TR/2008/TR_DCC-2008-018.pdf
Given a list N, take a random sample M less than N, such that each item in the list has an equal probability of being picked. It only requires a single pass through, & you don’t need to know the length of N.
Unless I misunderstood, though, in @insti’s case M = N, so reservoir sampling degenerates into a standard Fisher-Yates shuffle. This requires storing the whole list, which @insti specifically ruled out.
Robot Name
Write a program that manages robot factory settings.
When robots come off the factory floor, they have no name.
The first time you boot them up, a random name is generated, such as RX837 or BC811.
Every once in a while we need to reset a robot to its factory settings, which means that their name gets wiped. The next time you ask, it will respond with a new random name.
The names must be random: they should not follow a predictable sequence. Random names means a risk of collisions. Your solution should not allow the use of the same name twice when avoidable. In some exercism language tracks there are tests to ensure that the same name is never used twice.
In my solution. since the number of possible names is small (676,000), I just generated them all and shuffled the list and took them one at a time. But if the naming scheme is different and the number of names becomes impractical to pre-generate them all, the solution would be to randomly generate them and check for collisions against the names you’d already used. The issue then becomes, what happens when this list gets full and you’re trying to generate one of the few remaining numbers, your naive implementation is going to get stuck generating conflicting random numbers until it gets lucky.
So that led me to thinking about a (pseudo)random number sequence that would generate all the numbers I needed in O(1)* and you’d know when you were done because you’d hit your initial seed value.
However all the research I could find was concerned with finding generators that would have large periods that are able to generate a lot of random numbers and it weren’t concerned about covering every number exactly once.
* Well it would probably be O(n) to generate them all, but O(1) for each value.
Oh, the problem you linked to sounds a lot easier than the problem you stated originally. I think you can just make the name rand() + robot_num, where you increment robot_num each time you name one. So even if you generate the same random number, the robot_num will never match. Of course, the robot_num is predictable but overall the name is not.
