Быстрая генерация случайных нарушений

Question

Я хочу генерировать расстройств равномерно наугад. Другими словами: перемешать вектор так, чтобы ни один элемент не оставался на своем первоначальном месте .

Требования:

• равномерная выборка (каждое нарушение генерируется с равной вероятностью )
• практическая реализация быстрее, чем метод отклонения (т. Е. Продолжайте генерировать случайные перестановки, пока мы не найдем отклонение от нормы) либо не производите выборку равномерно (или не в состоянии доказать однородность), либо не проводите практическое сравнение с методом отклонения. Около 1/e = 37% перестановок являются отклонениями, что дает представление о том, какую производительность можно ожидать в лучшем случае относительно метода отбраковки.

  Единственная найденная мной ссылка, которая делает практическое сравнение, находится в этого тезиса , который оценивает 7,76 с для предложенного им алгоритма против 8,25 с для метода отклонения (см. Стр. 73). Это ускорение всего в 1,06 раза. Мне интересно, возможно ли что-то значительно лучшее (> 1,5).

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

Answer 1

Вот идея алгоритма, который может работать на вас. Создайте расстройство в циклической записи. Таким образом, (1 2) (3 4 5) представляет расстройство 2 1 4 5 3. (То есть (1 2) - это цикл, как и (3 4 5).)

Поместите первый элемент на первое место (в обозначении цикла вы всегда можете это сделать) и выберите случайную перестановку остальных. Теперь нам просто нужно выяснить, где круглые скобки go для длины цикла.

Как отмечает https://mathoverflow.net/questions/130457/the-distribution-of-cycle-length-in-random-derangement, в перестановке случайный цикл равномерно распределен по длине. Они не случайным образом распределены в расстройствах. Но число отклонений длины m равно m!/e, округляется в большую сторону для четных m и уменьшается до нечетных m. Итак, что мы можем сделать, это выбрать длину, равномерно распределенную в диапазоне 2..n, и принять ее с вероятностью того, что оставшиеся элементы, действуя случайным образом, будут являться нарушением. Эта длина цикла будет правильно распределена. И затем, как только у нас будет первая длина цикла, мы повторяем следующую до тех пор, пока не закончим.

Процедура, выполненная описанным мною способом, проще в реализации, но математически эквивалентна принятию случайного отклонения (отклонением), и записывать только первый цикл. Потом повторюсь. Поэтому можно доказать, что это вызывает все нарушения с равной вероятностью.

При таком наивном подходе мы будем брать в среднем 3 броска, прежде чем принять длину. Однако затем мы в среднем разрешили проблему пополам. Таким образом, число случайных чисел, которые нам нужно сгенерировать для размещения скобок, равно O(log(n)). По сравнению со O(n) случайными числами для построения перестановки это ошибка округления. Однако его можно оптимизировать, отметив, что наибольшая вероятность принятия составляет 0.5. Поэтому, если мы с двойной вероятностью примем вероятность случайного получения расстройства, если мы продолжим, наша крыса ios будет по-прежнему правильной, и мы избавимся от большинства наших отклонений длины цикла.

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

Answer 2

Пусть d (n) - число отклонений массива A длины n.

d(n) = (n-1) * (d(n-1) + d(n-2))

Расположение d (n) достигается:

1. First, swapping A[0] with one of the remaining n-1 elements
2. Next, either deranging all n-1 remaning elements, or deranging 
   the n-2 remaining that excludes the index 
   that received A[0] from the initial matrix.

Как Можем ли мы генерировать расстройство случайным образом равномерно?

1. Perform the swap of step 1 above.
2. Randomly decide which path we're taking in step 2,
   with probability d(n-1)/(d(n-1)+d(n-2)) of deranging all remaining elements.
3. Recurse down to derangements of size 2-3 which are both precomputed.

В Википедии d (n) = floor (n! / e + 0.5) (точно). Вы можете использовать это для вычисления вероятности шага 2 точно в постоянное время для малых n. Для больших n факториал может быть медленным, но все, что вам нужно, это соотношение. Это приблизительно (n-1) / n. Вы можете жить с приближением или предварительно вычислить и сохранить rat ios до максимально допустимого значения n.

Обратите внимание, что (n-1) / n очень быстро сходится.

Answer 3

Мне любопытно ... и математически не информирован. Поэтому я невинно спрашиваю, почему «простого тасования» не будет достаточно? начал. Каждый элемент будет перемещен «куда-то еще».

Answer 4

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

• Сначала выберите случайную (1, N) позицию для значения 1.
  • примечание: 1 to N вместо 0 to N-1 для простоты.
• , тогда для значения 2 позиция будет случайной (1, N-1), если 1 попадает на позицию 2 и случайным образом (1, N-2) в противном случае.
• все go будет проходить по списку и считать только еще не использованную позицию, пока не достигнет выбранной случайная позиция для значения 2, конечно, позиция 2 будет пропущена.
• для значения 3 al go проверит, если позиция 3 уже используется. если используется, pos3 = random(1,N-2), если нет, pos3 = random(1,N-3)
• снова, al go будет проходить по списку и считать только еще не использованную позицию, пока не достигнет счет = pos3. и затем поместите туда значение 3.
• . Это будет продолжаться для следующих значений, пока все значения не будут полностью помещены в позиции.

, и это сгенерирует равномерное отклонение вероятности.

Оптимизация будет сосредоточена на том, как быстро go достигнет pos#. вместо того, чтобы перемещаться по списку для подсчета еще не использованных позиций, al go может использовать несколько куч, как поиск позиций, которые еще не использовались, вместо подсчета и проверки позиций 1 на 1. или любых других методов, кроме кучи. -как поиска. это отдельная проблема, которую нужно решить: how to reached an unused item given it's position-count in a list of unused-items.