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

Here is a way to random without repeating results. It also works for strings. Its in C# but the logig should work in many places. Put the random results in a list and check if the new random element is in that list. If not than you have a new random element. If it is in that list, repeat the random until you get an element that is not in that list.

List<string> Erledigte = new List<string>();
private void Form1_Load(object sender, EventArgs e)
{
    label1.Text = "";
    listBox1.Items.Add("a");
    listBox1.Items.Add("b");
    listBox1.Items.Add("c");
    listBox1.Items.Add("d");
    listBox1.Items.Add("e");
}

private void button1_Click(object sender, EventArgs e)
{
    Random rand = new Random();
    int index=rand.Next(0, listBox1.Items.Count);
    string rndString = listBox1.Items[index].ToString();

    if (listBox1.Items.Count <= Erledigte.Count)
    {
        return;
    }
    else
    {
        if (Erledigte.Contains(rndString))
        {
            //MessageBox.Show("vorhanden");
            while (Erledigte.Contains(rndString))
            {
                index = rand.Next(0, listBox1.Items.Count);
                rndString = listBox1.Items[index].ToString();
            }
        }

        Erledigte.Add(rndString);
        label1.Text += rndString;
    }
}

Answer 2

A shuffle is the best you can do for random numbers in a specific range with no repeats. The reason that the method you describe (randomly generate numbers and put them in a Set until you reach a specified length) is less efficient is because of duplicates. Theoretically, that algorithm might never finish. At best it will finish in an indeterminable amount of time, as compared to a shuffle, which will always run in a highly predictable amount of time.

---

Response to edits and comments:

If, as you indicate in the comments, the range of numbers is very large and you want to select relatively few of them at random with no repeats, then the likelihood of repeats diminishes rapidly. The bigger the difference in size between the range and the number of selections, the smaller the likelihood of repeat selections, and the better the performance will be for the select-and-check algorithm you describe in the question.

Answer 3

Mersenne twister

Description of which can be found here on Wikipedia: Mersenne twister

Look at the bottom of the page for implementations in various languages.

Answer 4

If you can generate 'small' random numbers, you can generate 'large' random numbers by integrating them: add a small random increment to each 'previous'.

const size_t amount = 100; // a limited amount of random numbers
vector<long int> numbers; 
numbers.reserve( amount );
const short int spread = 250; // about 250 between each random number
numbers.push_back( myrandom( spread ) );
for( int n = 0; n != amount; ++n ) {
    const short int increment = myrandom( spread );
    numbers.push_back( numbers.back() + increment );
}

myshuffle( numbers );

The myrandom and myshuffle functions I hereby generously delegate to others :)

Answer 5

A shuffle is a perfectly good way to do this (provided you do not introduce a bias using the naive algorithm). See Fisher-Yates shuffle.

Answer 6

This answer suggests some strategies for getting what you want and ensuring they are in a random order using some already well-known algorithms.

There is an inside out version of the Fisher-Yates shuffle algorithm, called the Durstenfeld version, that randomly distributes sequentially acquired items into arrays and collections while loading the array or collection.

One thing to remember is that the Fisher-Yates (AKA Knuth) shuffle or the Durstenfeld version used at load time is highly efficient with arrays of objects because only the reference pointer to the object is being moved and the object itself doesn't have to be examined or compared with any other object as part of the algorithm.

I will give both algorithms further below.

If you want really huge random numbers, on the order of 1024 bytes or more, a really good random generator that can generate unsigned bytes or words at a time will suffice. Randomly generate as many bytes or words as you need to construct the number, make it into an object with a reference pointer to it and, hey presto, you have a really huge random integer. If you need a specific really huge range, you can add a base value of zero bytes to the low-order end of the byte sequence to shift the value up. This may be your best option.

If you need to eliminate duplicates of really huge random numbers, then that is trickier. Even with really huge random numbers, removing duplicates also makes them significantly biased and not random at all. If you have a really large set of unduplicated really huge random numbers and you randomly select from the ones not yet selected, then the bias is only the bias in creating the huge values for the really huge set of numbers from which to choose. A reverse version of Durstenfeld's version of the Yates-Fisher could be used to randomly choose values from a really huge set of them, remove them from the remaining values from which to choose and insert them into a new array that is a subset and could do this with just the source and target arrays in situ. This would be very efficient.

This may be a good strategy for getting a small number of random numbers with enormous values from a really large set of them in which they are not duplicated. Just pick a random location in the source set, obtain its value, swap its value with the top element in the source set, reduce the size of the source set by one and repeat with the reduced size source set until you have chosen enough values. This is essentiall the Durstenfeld version of Fisher-Yates in reverse. You can then use the Dursenfeld version of the Fisher-Yates algorithm to insert the acquired values into the destination set. However, that is overkill since they should be randomly chosen and randomly ordered as given here.

Both algorithms assume you have some random number instance method, nextInt(int setSize), that generates a random integer from zero to setSize meaning there are setSize possible values. In this case, it will be the size of the array since the last index to the array is size-1.

The first algorithm is the Durstenfeld version of Fisher-Yates (aka Knuth) shuffle algorithm as applied to an array of arbitrary length, one that simply randomly positions integers from 0 to the length of the array into the array. The array need not be an array of integers, but can be an array of any objects that are acquired sequentially which, effectively, makes it an array of reference pointers. It is simple, short and very effective

int size = someNumber;
int[] int array = new int[size]; // here is the array to load
int location; // this will get assigned a value before used
// i will also conveniently be the value to load, but any sequentially acquired
// object will work
for (int i = 0; i <= size; i++) { // conveniently, i is also the value to load
      // you can instance or acquire any object at this place in the algorithm to load
      // by reference, into the array and use a pointer to it in place of j
      int j = i; // in this example, j is trivially i
    if (i == 0) { // first integer goes into first location
        array[i] = j; // this may get swapped from here later
    } else { // subsequent integers go into random locations
            // the next random location will be somewhere in the locations
            // already used or a new one at the end
            // here we get the next random location
            // to preserve true randomness without a significant bias
            // it is REALLY IMPORTANT that the newest value could be
            // stored in the newest location, that is, 
            // location has to be able to randomly have the value i
            int location = nextInt(i + 1); // a random value between 0 and i
            // move the random location's value to the new location
            array[i] = array[location];
            array[location] = j; // put the new value into the random location
    } // end if...else
} // end for

Voila, you now have an already randomized array.

If you want to randomly shuffle an array you already have, here is the standard Fisher-Yates algorithm.

type[] array = new type[size];

// some code that loads array...

// randomly pick an item anywhere in the current array segment, 
// swap it with the top element in the current array segment,
// then shorten the array segment by 1
// just as with the Durstenfeld version above,
// it is REALLY IMPORTANT that an element could get
// swapped with itself to avoid any bias in the randomization
type temp; // this will get assigned a value before used
int location; // this will get assigned a value before used
for (int i = arrayLength -1 ; i > 0; i--) {
    int location = nextInt(i + 1);
    temp = array[i];
    array[i] = array[location];
    array[location] = temp;
} // end for

For sequenced collections and sets, i.e. some type of list object, you could just use adds/or inserts with an index value that allows you to insert items anywhere, but it has to allow adding or appending after the current last item to avoid creating bias in the randomization.