Требуется обновление браузера.

Выбор двух различных случайных элементов множества (генерация транспозиций)


Просмотров: 892
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
= 1. И вот тут начинаются костыли для используемой в задаче индексации с единицы:
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)
вернёт число 4.

Тогда:
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()
результата при помощи взятия остатка от деления. Так как значение "0" в качестве смещения от индекса A недопустимо (A и B совпадут), то, аналогично рассмотренной ранее ситуации (со сменой индексации), производится увеличение на единицу.

Вот и всё.

Запись опубликована в категориях:

Алгоритмы и аспекты  
 

Комментарии

Инкогнито
  Загружаем captcha