Generate sequence of integers in random order without constructing the whole list upfront

Question

How can I generate the list of integers from 1 to N but in a random order, without ever constructing the whole list in memory?

(To be clear: Each number in the generated list must only appear once, so it must be the equivalent to creating the whole list in memory first, then shuffling.)

This has been determined to be a duplicate of this question.

Answer 1

You will need at least half of the total list's memory, just to remember what you did already.

If you are in tough memory conditions, you may try so:

1. Keep the results generated so far in a tree, randomize the data, and insert it into the tree. If you cannot insert then generate another number and try again, etc, until the tree fills halfway.

2. When the tree fills halfway, you inverse it: you construct a tree holding numbers that you haven't used already, then pick them in random order.

It has some overhead for keeping the tree structure, but it may help when your pointers are considerably smaller in size than your data is.

Answer 2

Oops, my question is a duplicate of Generating shuffled range using a PRNG rather than shuffling.

Answer 3

It might help to specify a language you are searching a solution for.

You could use a dynamic list where you store your generated numbers, since you will need a reference which numbers you already created. Every time you create a new number you could check if the number is contained in the list and throw it away if it is contained and try again.

The only possible way without such a list would be to use a number size where it is unlikely to generate a duplicate like a UUID if the algorithm is working correctly - but this doesn't guarantee that no duplicate is generated - it is just highly unlikely.

Answer 4

very simple random is 1+((power(r,x)-1) mod p) will be from 1 to p for values of x from 1 to p and will be random where r and p are prime numbers and r <> p.

Answer 5

Not the whole list technically, but you could use a bit mask to decide if a number has already been selected. This has a lot less storage than the number list itself.

Set all N bits to 0, then for each desired number:

• use one of the normal linear congruent methods to select a number from 1 to N.
• if that number has already been used, find the next highest unused (0 bit), with wrap.
• set that numbers bit to 1 and return it.

That way you're guaranteed only one use per number and relatively random results.