0

I want to pick random numbers without repeats between 0 and a very large number, say, 2^64. I'll do this a lot of times and I don't have much RAM, so I can't just store the numbers that have already been used and compare each new number with that list. I know I could just store this list to a file, but that would be slow.

Is there an algorithm that can generate random numbers without repeats, that doesn't require all of the generated numbers to be stored somewhere? For example, it could be a function that takes a number from 0 to n as the input, and maps each possible input to a unique output from 0 to n. So, to generate, say, 100 random unique numbers, I can just call this function with arguments from 1 to 100. (I realize that such a function would not be "random," since every time it is called with the same input, it would give the same output. But the sequence of outputs would appear as random as any other pseudorandom number generator.)

So really this is three questions.

  • Is such an algorithm at all possible?
  • What would the pseudocode look like, if it is possible?
  • Is it practical to use in any realistic situation?

Note: There's a boatload of "random numbers no repeats" questions on here, but I didn't find any that had the "without storing already-used numbers" catch, so I don't think this is a duplicate.

ItsAmy
  • 844
  • 1
  • 6
  • 20
  • Some of the answers on [these](http://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1) [questions](http://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats?rq=1) looks like they should work. – Bernhard Barker Jul 16 '15 at 17:56
  • Ah, thank you! I had seen similar questions with answers that involved starting with a randomly shuffled list, then just returning sequential values from it, which does not fit my requirements, but the one you linked mentioned a LFSR. I'll look into that. – ItsAmy Jul 16 '15 at 18:05
  • One really easy way, using a multiplicative inverse: http://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/ – Jim Mischel Jul 17 '15 at 03:53
  • The general solutions are covered here: http://crypto.stackexchange.com/questions/1379/how-to-generate-a-list-of-unique-random-strings/1390#1390 In your case, use the third option, encryption, with a 64-bit block cipher, such as DES. – rossum Jul 18 '15 at 11:16

0 Answers0