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

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

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

Пример в только что изобретенном псевдокоде С# -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

Ответы

Ответ 1

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

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

Ответ 3

Одно предложение, но интенсивность памяти:

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

Ответ 4

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

Основная проблема заключается в том, что типичные контейнеры не могут справиться с этим эффективно. Я использовал его с битовыми векторами, но он работает только хорошо, если максимально возможный член достаточно мал из-за линейного сканирования битвектора, необходимого для поиска 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 потенциально различается каждый раз. Большинство стандартных случайных генераторов дают фиксированный диапазон. Хотя следующее НЕ дает равномерного распределения, это часто достаточно хорошо...

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

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

Ответ 5

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

В основном вы начинаете с упорядоченного 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

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

Ответ 6

  • Возьмите все числа в интервале, поместите их в список/массив
  • Shuffle список/массив
  • Перебирать список/массив

Ответ 7

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

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

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

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