Выбор двух различных случайных элементов множества (генерация транспозиций)
Просмотров: 2071
01 февраля 2016 года
Постановка задачи
При реализации некоторых задач, Вам может потребоваться обеспечить выборку двух случайных объектов из множества, при этом объекты должны быть обязательно разными. Например, Вы хотите перемешать массив перестановками элементов, но не желаете тратить процессорное время на вырожденные перестановки вида v[j]⇄v[j]. Или Вы индицируете активность системы, случайным образом меняя выбранный элемент - выбор одного и того же элемента два раза подряд недопустим.
В попытках решить проблему, некоторые программисты не брезгуют жуткими созданиями, типа:
- генерация индекса A;
- генерация индекса B;
- если B равен A - перейти к пункту 2;
- готово;
Такой алгоритм обладает произвольным временем выполнения. Я предлагаю (наверняка, кто-то уже до этого додумался ранее) подход, выбирающий два элемента за короткое постоянное время (при условии независимости времени выполнения арифметических операций от значения аргументов).
Итак, постановка задачи.
Реализовать псевдослучайную генерацию двух индексов A и B (чисел, принимающих дискретные значения [1;N]; N>1). Индексы A и B не должны совпадать. Алгоритм должен позволять осуществить генерацию за фиксированное время.
Решение
Представим массив, как набор фишек:
Упорядочим фишки, присвоив им индексы (сверху вниз). Очевидно, выбрать первый случайны элемент не составит труда (разумеется, если среда имеет генератор чисел):
Генерация A
1 | A=Rand(1,N)
|
Допустим, A=3:
Собственно, вот тут-то проблемы и начинаются. Массив разбивается выбранным индексом A на две части (а может и нет). Генерировать ещё одно случайное число для выбора части не хочется: лишний раз теребить генератор, потенциально создавая нежелательные статистические эффекты.
Весь трюк предлагаемого подхода - замкнуть концы массива в кольцо:
Теперь для выбора доступно (N-1) элементов, начиная с (A+1).
Арифметически, кольцо можно реализовать при помощи взятия остатка от деления. Действительно: взятие остатка от деления некоего числа (x+z) на некий x даёт z. Например:
(4+1) mod 4
x mod xКонструкция дорабатывается переходом сперва к индексации с нуля (-1), а затем - обратно (+1).
Вместо
z mod x((z-1) mod x)+1
Чтобы получать числа, не превосходящие (x-1), надо брать остаток от деления на x. Так как, при реализации кольца, мы работаем с индексацией от нуля, максимальный индекс для массива из N элементов равен (N-1). Исходя из сказанного, необходимо брать остаток от деления на N.
Таким образом, окончательная формула будет иметь вид:
Генерация B
1 | B=((A+Rand(1,N-1)-1) Mod N)+1
|
Конкретно в нашем случае:
B=((3+Rand(1,8-1)-1) Mod 8)+1
B=((3+Rand(1,7)-1) Mod 8)+1
Допустим, вызов
Rand(1,7)
Тогда:
B=((3+Rand(1,7)-1) Mod 8)+1
B=((3+4-1) Mod 8)+1
B=(6 Mod 8)+1
B=6+1
B=7
Таким образом, B=7, или, в другой интерпретации: B отстоит от A (включая B) на 4 элемента. Именно число 4 вернул генератор при вызове
Rand(1,7)
Так как закольцовывание массива было реализовано на уровне формул для индексации элементов, никаких дополнительных работ проводить не надо:
Решение при индексации с нуля
Скорректируем формулировку задачи.
Реализовать псевдослучайную генерацию двух индексов A и B (чисел, принимающих дискретные значения [0;N-1]; N>1). Индексы A и B не должны совпадать. Алгоритм должен позволять осуществить генерацию за фиксированное время.
В качестве языка, в котором элементы массивов индексируются с нуля, выберем C++.
Генерация A и B
12 | unsigned A=rand()%N; unsigned B=(A+1+rand()%(N-1))%N; |
Занятно, что при генерации B (по сравнению с предыдущим решением) в скобках не только пропадает "-1", но и появляется "+1". Данное обстоятельство связано с сужением возвращаемого функцией
rand()Вот и всё.
Комментарии