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

This has been asked before - see my answer to the previous question. In a nutshell: You can use a block cipher to generate a secure (random) permutation over any range you want, without having to store the entire permutation at any point.

Answer 2

Assuming you have a random or pseudo-random number generator, even if it's not guaranteed to return unique values, you can implement one that returns unique values each time using this code, assuming that the upper limit remains constant (i.e. you always call it with random(10), and don't call it with random(10); random(11).

The code doesn't check for errors. You can add that yourself if you want to.
It also requires a lot of memory if you want a large range of numbers.

/* the function returns a random number between 0 and max -1
 * not necessarily unique
 * I assume it's written
 */
int random(int max);

/* the function returns a unique random number between 0 and max - 1 */
int unique_random(int max)
{

    static int *list = NULL;    /* contains a list of numbers we haven't returned */
    static int in_progress = 0; /* 0 --> we haven't started randomizing numbers
                                 * 1 --> we have started randomizing numbers
                                 */

    static int count;
    static prev_max = 0;

    // initialize the list
    if (!in_progress || (prev_max != max)) {
        if (list != NULL) {
            free(list);
        }
        list = malloc(sizeof(int) * max);
        prev_max = max;
        in_progress = 1;
        count = max - 1;

        int i;
        for (i = max - 1; i >= 0; --i) {
            list[i] = i;
        }
    }

    /* now choose one from the list */
    int index = random(count);
    int retval = list[index];

    /* now we throw away the returned value.
     * we do this by shortening the list by 1
     * and replacing the element we returned with
     * the highest remaining number
     */
    swap(&list[index], &list[count]);

    /* when the count reaches 0 we start over */
    if (count == 0) {
        in_progress = 0;
        free(list);
        list = 0;
    } else { /* reduce the counter by 1 */
        count--;
    }
}

/* swap two numbers */
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

Answer 3

static std::unordered_set<long> s;
long l = 0;
for(; !l && (s.end() != s.find(l)); l = generator());
v.insert(l);

generator() being your random number generator. You roll numbers as long as the entry is not in your set, then you add what you find in it. You get the idea.

I did it with long for the example, but you should make that a template if your PRNG is templatized.

Alternative is to use a cryptographically secure PRNG that will have a very low probability to generate twice the same number.

Answer 4

What about using GUID generator (like in the one in .NET). Granted it is not guaranteed that there will be no duplicates, however the chance getting one is pretty low.

Answer 5

The problem is to select a "random" sequence of N unique numbers from the range 1..M where there is no constraint on the relationship between N and M (M could be much bigger, about the same, or even smaller than N; they may not be relatively prime).

Expanding on the linear feedback shift register answer: for a given M, construct a maximal LFSR for the smallest power of two that is larger than M. Then just grab your numbers from the LFSR throwing out numbers larger than M. On average, you will throw out at most half the generated numbers (since by construction more than half the range of the LFSR is less than M), so the expected running time of getting a number is O(1). You are not storing previously generated numbers so space consumption is O(1) too. If you cycle before getting N numbers then M less than N (or the LFSR is constructed incorrectly).

You can find the parameters for maximum length LFSRs up to 168 bits here (from wikipedia): http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Here's some java code:

/** * Generate a sequence of unique "random" numbers in [0,M) * @author dkoes * */

public class UniqueRandom { long lfsr; long mask; long max;

private static long seed = 1;
//indexed by number of bits
private static int [][] taps = {
        null, // 0
        null, // 1
        null, // 2
        {3,2}, //3
        {4,3},
        {5,3},
        {6,5},
        {7,6},
        {8,6,5,4},
        {9,5},
        {10,7},
        {11,9},
        {12,6,4,1},
        {13,4,3,1},
        {14,5,3,1},
        {15,14},
        {16,15,13,4},
        {17,14},
        {18,11},
        {19,6,2,1},
        {20,17},
        {21,19},
        {22,21},
        {23,18},
        {24,23,22,17},
        {25,22},
        {26,6,2,1},
        {27,5,2,1},
        {28,25},
        {29,27},
        {30,6,4,1},
        {31,28},
        {32,22,2,1},
        {33,20},
        {34,27,2,1},
        {35,33},
        {36,25},
        {37,5,4,3,2,1},
        {38,6,5,1},
        {39,35},
        {40,38,21,19},
        {41,38},
        {42,41,20,19},
        {43,42,38,37},
        {44,43,18,17},
        {45,44,42,41},
        {46,45,26,25},
        {47,42},
        {48,47,21,20},
        {49,40},
        {50,49,24,23},
        {51,50,36,35},
        {52,49},
        {53,52,38,37},
        {54,53,18,17},
        {55,31},
        {56,55,35,34},
        {57,50},
        {58,39},
        {59,58,38,37},
        {60,59},
        {61,60,46,45},
        {62,61,6,5},
        {63,62},
};

//m is upperbound; things break if it isn't positive
UniqueRandom(long m)
{
    max = m;
    lfsr = seed; //could easily pass a starting point instead
    //figure out number of bits
    int bits = 0;
    long b = m;
    while((b >>>= 1) != 0)
    {
        bits++;
    }
    bits++;

    if(bits < 3)
        bits = 3; 

    mask = 0;
    for(int i = 0; i < taps[bits].length; i++)
    {
        mask |= (1L << (taps[bits][i]-1));
    }

}

//return -1 if we've cycled
long next()
{
    long ret = -1;
    if(lfsr == 0)
        return -1;
    do {
        ret = lfsr;
        //update lfsr - from wikipedia
        long lsb = lfsr & 1;
        lfsr >>>= 1;
        if(lsb == 1)
            lfsr ^= mask;

        if(lfsr == seed)            
            lfsr = 0; //cycled, stick

        ret--; //zero is stuck state, never generated so sub 1 to get it
    } while(ret >= max);

    return ret;
}

}

Answer 6

If you want to creating large (say, 64 bits or greater) random numbers with no repeats, then just create them. If you're using a good random number generator, that actually has enough entropy, then the odds of generating repeats are so miniscule as to not be worth worrying about.

For instance, when generating cryptographic keys, no one actually bothers checking to see if they've generated the same key before; since you're trusting your random number generator that a dedicated attacker won't be able to get the same key out, then why would you expect that you would come up with the same key accidentally?

Of course, if you have a bad random number generator (like the Debian SSL random number generator vulnerability), or are generating small enough numbers that the birthday paradox gives you a high chance of collision, then you will need to actually do something to ensure you don't get repeats. But for large random numbers with a good generator, just trust probability not to give you any repeats.