1

I am unsure how to put this and my math skills aren't that strong. But here's what I need.

I want to generate a list of all the 16bit integers (0-65535). But everytime I do so I want to seed the algorithm randomly that each time the list starts with a different integer and all the subsequent integers will be generated once but also in random order.

small example (1-5): ...

1, 5, 3, 2, 4

4, 3, 1, 5, 2

2, 1, 4, 5, 3 ...

Any help?

vvv
  • 11
  • 1
  • Of course I could do this by generating a random number in the range, then generating a new one, whilst checking if it has not been generated yet and so forth but this will slow down the algorithm really badly if I need to use generate large amounts of integers (in the 2^32 range) – vvv Mar 31 '10 at 10:09
  • The solutions proposed by Luke and others are very reasonable as long as you can keep the whole range in memory. If that is not the case then you'd probably have to use some pseudorandom permuation and the solution depends on how good that pseudorandom permuation has to be. E.g., do you have attackers that could benefit from predicting a pseudorandom sequence? Since your question seems to be somewhat different from what you are looking for and your requirements are still unclear, I'd suggest to open another question with a better description of what you are looking for. – abc Mar 31 '10 at 11:04
  • possible duplicate of http://stackoverflow.com/questions/162606/iterating-shuffled-0-n-without-arrays – Jason S Mar 31 '10 at 11:56

3 Answers3

4

The easiest way is probably to generate the list of required numbers and then shuffle it.

LukeH
  • 263,068
  • 57
  • 365
  • 409
  • 1
    That works, but what if I need to generate a list of 2^31 integers? Is there an algorithm thinkable with which I can only retain the state of the initial seed + the last generated number and then just call get_next_number() on it ? That would be way faster. – vvv Mar 31 '10 at 10:14
  • [code] unsigned int random_seed = 0; unsigned int sample_size = 3000; unsigned int generated_number = random_seed % sample_size; unsigned int prime_number = 7; unsigned int increment = prime_number; for(unsigned int iterator = 0; iterator < sample_size; ++iterator) { generated_number = (generated_number + increment) % sample_size; } http://en.wikipedia.org/wiki/Full_cycle [/code] – vvv Mar 31 '10 at 10:29
  • I think you might be able to do that using a Linear Feedback Shift Register. I guess you'd need to use a 32-bit LFSR and ensure that it was setup correctly to return the max length sequence. (Disclaimer: I know nothing about this topic, so I could be completely wrong!) – LukeH Mar 31 '10 at 10:30
  • See http://en.wikipedia.org/wiki/Linear_feedback_shift_register and http://en.wikipedia.org/wiki/Maximum_length_sequence for more info. – LukeH Mar 31 '10 at 10:30
3

Assuming you have no security requirements, possibly the easiest method is to create a Linear Congruential Generator (LCG) and select a new multiplier and/or increment every time you need to change the sequence. Using the notation from the Wikipedia entry, if you want all k-bit integers, your modulus is m=2k and conditions 1, 2, and 3 simplify to:
1. c is odd
2. a = 1 + 4*x for any integer x

There are other generators that are similar to LCG that should be just as satisfactory.

President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
1
  1. Create a list of integers. In your example from 1 to 5 inclusive;
  2. Perform a correct shuffle on it. For example, the Fisher-Yates shuffle. The "correct" part is important as an incorrect shuffle algorithm will yield biased results.

You don't say what language you use but here are two:

PHP

$arr = range(1, 5);
shuffle($arr);

Java

List<Integer> list = new ArrayList<Integer>();
for (int i=1; i<=5; i++) {
  list.add(i);
}
Collections.shuffle(list);
cletus
  • 616,129
  • 168
  • 910
  • 942