Какие алгоритмы перетасовки существуют помимо Фишера-Йейтса и поиска «следующей перестановки»?

Question

В частности, в области одномерных наборов элементов одного типа, таких как вектор целых чисел.

Скажем, например, у вас был вектор размером 32 768, содержащий отсортированные целые числа от 0 до 32 767.

То, что я имею в виду под "следующей перестановкой", подразумевает выполнение следующей перестановки в лексической системе упорядочения.

Википедия перечисляет два , и мне интересно, есть ли еще (кроме чего-то bogo: P)

Answer 1

O (N) реализация Это основано на картировании Эяля Шнайдера Zn! -> P (n)

def get_permutation(k, lst):
    N = len(lst)
    while N:
        next_item = k/f(N-1)
        lst[N-1], lst[next_item] = lst[next_item], lst[N-1]
        k = k - next_item*f(N-1)
        N = N-1
    return lst

Это уменьшает его алгоритм O (N ^ 2), объединяя шаг преобразования с нахождением перестановки. По сути, он имеет ту же форму, что и Фишер-Йейтс, но заменяет вызов random на следующий шаг отображения. Если отображение на самом деле является биекцией (которую я работаю, чтобы доказать), то это лучший алгоритм, чем Фишер-Йейтс, потому что он вызывает генератор псевдослучайных чисел только один раз и поэтому будет более эффективным. Также обратите внимание, что это возвращает действие перестановки (N! - k), а не перестановки k, но это не имеет большого значения, потому что если k равномерно на [0, N!], То и N! - к.

старый ответ

Это немного связано с идеей "следующей" перестановки. Если предметы могут быть хорошо упорядочены, то можно построить лексикографическое упорядочение по перестановкам. Это позволяет построить карту из целых чисел в пространство перестановок.

Тогда нахождение случайной перестановки эквивалентно выбору случайного целого числа от 0 до N! и построение соответствующей перестановки. Этот алгоритм будет столь же эффективным (и столь же сложным для реализации), как и вычисление n-й перестановки рассматриваемого множества. Это тривиально дает равномерный выбор перестановки, если наш выбор n является равномерным.

Немного подробнее о порядке перестановок. учитывая набор S = {a b c d}, математики рассматривают набор перестановок S как группу с операцией композиции. если p является одной перестановкой, скажем, (b a c d), то p работает на S, переводя b в a, a в c, c в d и d в b. если q - другая перестановка, скажем, (d b c a), тогда pq получается, сначала применяя q, а затем p, что дает (d a b)(c). например, q переводит d в b, а p переводит b в a, так что pq переводит d в a. Вы увидите, что pq имеет два цикла, потому что он принимает b к d и исправляет c. Обычно пропускают 1 цикл, но я оставил это для ясности.

Мы собираемся использовать некоторые факты из теории групп.

1. непересекающиеся циклы коммутируют. (a b)(c d) совпадает с (c d)(a b)
2. мы можем расположить элементы в цикле в любом циклическом порядке. то есть (a b c) = (b c a) = (c a b)

Итак, учитывая перестановку, упорядочите циклы так, чтобы самые большие циклы были первыми. Когда два цикла имеют одинаковую длину, расположите их элементы так, чтобы на первом месте находился самый большой (мы всегда можем заказать счетный набор, даже если он произвольно так). Тогда у нас просто есть лексикографический порядок сначала по длине циклов, а затем по их содержанию. Это хорошо упорядочено, потому что две перестановки, которые состоят из одинаковых циклов, должны быть одной и той же перестановкой, поэтому если p > q и q > p, то p = q.

Этот алгоритм может быть тривиально выполнен за O (N! LogN! + N!) Время. просто создайте все перестановки (РЕДАКТИРОВАТЬ: просто, чтобы было ясно, я надел шляпу математика, когда я предложил это, и в любом случае это был язык в щеке), быстро отсортируйте их и найдите n-ное. Это другой алгоритм, чем тот, который вы упомянули.

Answer 2

Вот идея о том, как улучшить aaronasterling ответ.Это позволяет избежать генерации всего N!перестановки и сортировка их в соответствии с их лексикографическим порядком, и, следовательно, имеет намного лучшую временную сложность.

Внутренне он использует необычное представление перестановок, которое имитирует процесс выбора и удаления из сокращающегося массива.Например, последовательность <0,1,0> представляет перестановку, полученную в результате удаления элемента № 0 из [0,1,2], затем удаления элемента № 1 из [1,2] и удаления элемента № 0 из [1].Результирующая перестановка составляет <0,2,1>.При таком представлении первая перестановка всегда будет <0,0, ... 0>, а последняя всегда будет,Я назову это специальное представление «представлением массива».

Ясно, что представление массива размера N может быть преобразовано в стандартное представление перестановки за O (N ^ 2) время, используя массив и уменьшая егокогда необходимо.

Следующая функция может использоваться для возврата K-й перестановки на {0,1,2 ..., N-1} в представлении массива:

getPermutation(k, N) {
    while(N > 0) {
        nextItem = floor(k / (N-1)!)
        output nextItem
        k = k - nextItem * (N-1)!
        N = N - 1
    }
}

Этот алгоритм работаетза время O (N ^ 2) (из-за преобразования представления) вместо времени O (N! log N).

- Пример -

getPermutation (4,3)возвращает <2,0,0>.Это представление массива соответствует, которая действительно является перестановкой по индексу 4 в упорядоченном списке перестановок на {A, B, C}:

ABC
ACB
BAC
BCA
CAB
CBA

Answer 3

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

В частности, при объединении двух списков вы выбираете новый элемент заголовка случайным образом, а не выбираете его какмаленький элемент головы.Вероятность выбора элемента из первого списка должна быть n/(n+m), где n - длина первого и m длина второго списка, чтобы это работало.

Я написалподробное объяснение здесь: Случайные перестановки и сортировка .

Answer 4

Другая возможность - построить LFSR или PRNG с периодом, равным количеству элементов, которые вы хотите.

Answer 5

Начните с отсортированного массива. Выберите 2 случайных индекса, переключите элементы в этих индексах. Повторите O (n lg n) раз.

Вам нужно повторить O (n lg n) раз, чтобы убедиться, что распределение приближается к однородному. (Вы должны убедиться, что каждый индекс выбран по крайней мере один раз, что является проблемой с шариками.)