Random number generator that fills an interval

Question

How would you implement a random number generator that, given an interval, (randomly) generates all numbers in that interval, without any repetition?

It should consume as little time and memory as possible.

Example in a just-invented C#-ruby-ish pseudocode:

interval = new Interval(0,9)
rg = new RandomGenerator(interval);
count = interval.Count // equals 10
count.times.do{
    print rg.GetNext() + " "
}

This should output something like :

1 4 3 2 7 5 0 9 8 6 

Answer 1

Fill an array with the interval, and then shuffle it.

The standard way to shuffle an array of N elements is to pick a random number between 0 and N-1 (say R), and swap item[R] with item[N]. Then subtract one from N, and repeat until you reach N =1.

Answer 2

One suggestion, but it's memory intensive:

The generator builds a list of all numbers in the interval, then shuffles it.

Answer 3

1. Take all numbers in the interval, put them to list/array
2. Shuffle the list/array
3. Loop over the list/array

Answer 4

One way is to generate an ordered list (0-9) in your example.

Then use the random function to select an item from the list. Remove the item from the original list and add it to the tail of new one.

The process is finished when the original list is empty.

Output the new list.

Answer 5

An occasionally useful alternative to the shuffle approach is to use a subscriptable set container. At each step, choose a random number 0 <= n < count. Extract the nth item from the set.

The main problem is that typical containers can't handle this efficiently. I have used it with bit-vectors, but it only works well if the largest possible member is reasonably small, due to the linear scanning of the bitvector needed to find the nth set bit.

99% of the time, the best approach is to shuffle as others have suggested.

EDIT

I missed the fact that a simple array is a good "set" data structure - don't ask me why, I've used it before. The "trick" is that you don't care whether the items in the array are sorted or not. At each step, you choose one randomly and extract it. To fill the empty slot (without having to shift an average half of your items one step down) you just move the current end item into the empty slot in constant time, then reduce the size of the array by one.

For example...

class remaining_items_queue
{
  private:
    std::vector<int>  m_Items;

  public:
    ...

    bool Extract (int &p_Item);  //  return false if items already exhausted
};

bool remaining_items_queue::Extract (int &p_Item)
{
  if (m_Items.size () == 0)  return false;

  int l_Random = Random_Num (m_Items.size ());
    //  Random_Num written to give 0 <= result < parameter

  p_Item = m_Items [l_Random];

  m_Items [l_Random] = m_Items.back ();
  m_Items.pop_back ();
}

The trick is to get a random number generator that gives (with a reasonably even distribution) numbers in the range 0 to n-1 where n is potentially different each time. Most standard random generators give a fixed range. Although the following DOESN'T give an even distribution, it is often good enough...

int Random_Num (int p)
{
  return (std::rand () % p);
}

std::rand returns random values in the range 0 <= x < RAND_MAX, where RAND_MAX is implementation defined.

Answer 6

A very efficient way to shuffle an array of numbers where each index is unique comes from image processing and is used when applying techniques like pixel-dissolve.

Basically you start with an ordered 2D array and then shift columns and rows. Those permutations are by the way easy to implement, you can even have one exact method that will yield the resulting value at x,y after n permutations.

The basic technique, described on a 3x3 grid:

1) Start with an ordered list, each number may exist only once

0 1 2
3 4 5
6 7 8

2) Pick a row/column you want to shuffle, advance it one step. In this case, i am shifting the second row one to the right.

0 1 2
5 3 4
6 7 8

3) Pick a row/column you want to shuffle... I suffle the second column one down.

0 7 2
5 1 4
6 3 8

4) Pick ... For instance, first row, one to the left.

2 0 7
5 1 4
6 3 8

You can repeat those steps as often as you want. You can always do this kind of transformation also on a 1D array. So your result would be now [2, 0, 7, 5, 1, 4, 6, 3, 8].

Answer 7

This has come up before. Try using a linear feedback shift register.