Генератор случайных чисел, заполняющий интервал

Question

Как бы вы реализовали генератор случайных чисел, который при заданном интервале (случайным образом) генерирует все числа в этом интервале без повторения?

Он должен занимать как можно меньше времени и памяти.

Пример только что изобретенного псевдокода C # -ruby-ish:

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

Это должно вывести что-то вроде:

1 4 3 2 7 5 0 9 8 6 

Answer 1

Заполните массив интервалом, а затем перемешайте его.

Стандартный способ перемешать массив из N элементов - выбрать случайное число от 0 до N-1 (скажем, R) и поменять элемент [R] на элемент [N]. Затем вычтите одно из N и повторяйте, пока не достигнете N = 1.

Answer 2

Это уже дошло. Попробуйте использовать линейную обратную связь shift регистр .

Answer 3

Очень эффективный способ перестановки массива чисел, каждый индекс которого уникален, исходит от обработки изображений и используется при применении таких методов, как растворение пикселей.

По сути, вы начинаете с упорядоченного 2D-массива, а затем смещаете столбцы и строки. Эти перестановки, кстати, легко реализовать, у вас может быть даже один точный метод, который даст результирующее значение в x, y после n перестановок.

Основная техника, описанная на сетке 3x3:

1) Начните с упорядоченного списка, каждый номер может существовать только один раз

0 1 2
3 4 5
6 7 8

2) Выберите строку / столбец, который вы хотите перемешать, продвиньте его на один шаг. В этом случае я сдвигаю второй ряд вправо.

0 1 2
5 3 4
6 7 8

3) Выберите строку / столбец, который вы хотите перетасовать ... Я перенес второй столбец на один.

0 7 2
5 1 4
6 3 8

4) Выбрать ... Например, первый ряд, один слева.

2 0 7
5 1 4
6 3 8

Вы можете повторять эти шаги так часто, как хотите. Вы всегда можете сделать такое преобразование также на одномерном массиве. Таким образом, ваш результат будет сейчас [2, 0, 7, 5, 1, 4, 6, 3, 8].

Answer 4

время от времени полезной альтернативой подходу shuffle является использование дополнительного набора контейнеров.На каждом шаге выберите случайное число 0 <= n <count.Извлеките n-й элемент из набора. </p>

Основная проблема заключается в том, что типичные контейнеры не могут справиться с этим эффективно.Я использовал его с битовыми векторами, но он работает хорошо только в том случае, если максимально возможный элемент достаточно мал из-за линейного сканирования битового вектора, необходимого для поиска n-го установленного бита.

99% временилучший подход - это перемешать, как предлагали другие.

РЕДАКТИРОВАТЬ

Я упустил тот факт, что простой массив - это хорошая "заданная" структура данных - неСпроси меня почему, я использовал это раньше.«Хитрость» заключается в том, что вам все равно, отсортированы ли элементы в массиве или нет.На каждом шаге вы выбираете один случайным образом и извлекаете его.Чтобы заполнить пустую ячейку (без необходимости сдвигать среднюю половину ваших элементов на один шаг вниз), вы просто перемещаете текущий конечный элемент в пустую ячейку за постоянное время, а затем уменьшаете размер массива на единицу.

Например ...

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 ();
}

Хитрость заключается в том, чтобы получить генератор случайных чисел, который выдает (с достаточно равномерным распределением) числа в диапазоне от 0 до n-1, где n потенциально каждый раз отличается.Большинство стандартных генераторов случайных чисел дают фиксированный диапазон.Хотя следующие DOESN'T дают равномерное распределение, оно часто достаточно хорошее ...

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

std :: rand возвращает случайные значения в диапазоне 0 <= x <RAND_MAXгде RAND_MAX определяется реализацией. </p>

Answer 5

Одно предложение, но оно занимает много памяти:

Генератор создает список всех чисел в интервале, а затем перемешивает его.

Answer 6

Вы можете использовать линейный конгруэнтный генератор с параметрами, выбранными случайным образом, но так, чтобы он генерировал полный период. Вы должны быть осторожны, потому что качество случайных чисел может быть плохим, в зависимости от параметров.

Answer 7

Один из способов - создать упорядоченный список (0-9) в вашем примере.

Затем используйте случайную функцию, чтобы выбрать элемент из списка. Удалите элемент из исходного списка и добавьте его в конец нового.

Процесс завершается, когда исходный список пуст.

Вывести новый список.

Answer 8

1. Взять все числа в интервале, поместить их в список / массив
2. Перемешать список / массив
3. Зацикливать список / массив