Create Random Number Sequence with No Repeats

Question

Duplicate:

Unique random numbers in O(1)?

I want an pseudo random number generator that can generate numbers with no repeats in a random order.

For example:

random(10)

might return 5, 9, 1, 4, 2, 8, 3, 7, 6, 10

Is there a better way to do it other than making the range of numbers and shuffling them about, or checking the generated list for repeats?

---

Edit:

Also I want it to be efficient in generating big numbers without the entire range.

---

Edit:

I see everyone suggesting shuffle algorithms. But if I want to generate large random number (1024 byte+) then that method would take alot more memory than if I just used a regular RNG and inserted into a Set until it was a specified length, right? Is there no better mathematical algorithm for this.

Answer 1

Shuffling N elements doesn't take up excessive memory...think about it. You only swap one element at a time, so the maximum memory used is that of N+1 elements.

Answer 2

Suppose you wanted to generate a series of 256 random numbers without repeats.

1. Create a 256-bit (32-byte) memory block initialized with zeros, let's call it b
2. Your looping variable will be n, the number of numbers yet to be generated
3. Loop from n = 256 to n = 1
4. Generate a random number r in the range [0, n)
5. Find the r-th zero bit in your memory block b, let's call it p
6. Put p in your list of results, an array called q
7. Flip the p-th bit in memory block b to 1
8. After the n = 1 pass, you are done generating your list of numbers

Here's a short example of what I am talking about, using n = 4 initially:

**Setup**
b = 0000
q = []

**First loop pass, where n = 4**
r = 2
p = 2
b = 0010
q = [2]

**Second loop pass, where n = 3**
r = 2
p = 3
b = 0011
q = [2, 3]

**Third loop pass, where n = 2**
r = 0
p = 0
b = 1011
q = [2, 3, 0]

** Fourth and final loop pass, where n = 1**
r = 0
p = 1
b = 1111
q = [2, 3, 0, 1]

Answer 3

I asked a similar question before but mine was for the whole range of a int see Looking for a Hash Function /Ordered Int/ to /Shuffled Int/

Answer 4

If you don't mind mediocre randomness properties and if the number of elements allows it then you could use a linear congruential random number generator.

Answer 5

Actually, there's a minor point to make here; a random number generator which is not permitted to repeat is not random.

Answer 6

now we have a array with different numbers!

int main() {
    int b[(the number
    if them)];
    for (int i = 0; i < (the number of them); i++) {
    int a = rand() % (the number of them + 1) + 1;
    int j = 0;
    while (j < i) {
        if (a == b[j]) {
        a = rand() % (the number of them + 1) + 1;
        j = -1;
        }
        j++;
    }
    b[i] = a;
    }
}