Алгоритм линейного перемешивания на месте

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

У Mathworld есть краткая страница о риффл-тасовке . В частности, меня интересует разновидность out-shuffle, которая преобразует входной массив 1 2 3 4 5 6 в 1 4 2 5 3 6. Обратите внимание, что в их определении длина ввода равна .$2n$

Это просто выполнить за линейное время, если у нас есть второй массив размером или более удобный. Сначала скопируйте последние n элементов в массив. Затем, предполагая индексирование на основе 0, скопируйте первые n элементов из индексов [0,1,2, ..., n-1] в [0, 2, 4, ..., 2n-2] . Затем скопируйте n элементов из второго массива обратно во входной массив, сопоставив индексы [0,1,2, ..., n-1] с [1,3,5, ..., 2n-1] . (Мы можем сделать немного меньше, чем это, потому что первый и последний элементы на входе не перемещаются.)$n$$n$$n$$[0,1,2,...,n-1]$$[0, 2, 4,...,2n-2]$$n$$[0,1,2,...,n-1]$$[1,3,5,...,2n-1]$

Один из способов сделать это на месте заключается в разложении перестановки на непересекающиеся циклы, а затем переупорядочении элементов в соответствии с каждым циклом. Опять же, при условии индексации на основе 0 перестановка, включенная в случай с 6 элементами, выглядит так:

$$\sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}.$$

Как и ожидалось, первый и последний элементы являются фиксированными точками, и если мы переставим средние 4 элемента, мы получим ожидаемый результат.

К сожалению, мое понимание математики перестановок (и их ) в основном основано на википедии, и я не знаю, можно ли это сделать за линейное время. Может быть, перестановки, связанные с этой перестановкой, можно быстро разложить? Кроме того, нам даже не нужно полное разложение. Достаточно просто определить один элемент каждого из непересекающихся циклов, поскольку мы можем восстановить цикл по одному из его элементов. Возможно, нужен совершенно другой подход.$\LaTeX$

Хорошие ресурсы по смежной математике так же ценны, как и алгоритм. Благодарность!

Проблема на удивление нетривиальна. Вот хорошее решение Эллиса и Маркова « Стабильное слияние на месте» с помощью Perfect Shuffle (раздел 7). Эллис, Кран и Фан, « Вычисление циклов в совершенной перестановке», успешно выбирают «лидеров циклов» за счет увеличения объема памяти. Также связана хорошая статья Fich, Munro и Poblete , « Перестановка на месте» , которая дает общий алгоритм времени для модели оракула. Если доступен только оракул для перестановки, алгоритм требует логарифмического пространства; если у нас также есть оракул для обратного, он требует постоянного пространства.$O(n\log n)$

Теперь о решении Эллиса и Маркова. Сначала предположим, что . Затем вычисление совершенного перемешивания порядка сводится к вычислению совершенного перемешивания порядков и с вращением, предшествующим им. Вот доказательство на примере ( , , ): n x y n = 5 x = 3 y = 2 012 345 67 89 012 567 34 89 051627 $n = x+y$$n$$x$$y$$n=5$$x=3$$y=2$

$$\begin{array}{cc} 012\mathbf{345} & \mathbf{67}89 \\ 012\mathbf{567} & \mathbf{34}89 \\ 051627 & 3849 \end{array}$$

Эллис и Марков нашли простой способ вычислить идеальное перемешивание при , используя постоянное пространство и линейное время. Используя это, мы получаем алгоритм для вычисления идеального перемешивания для произвольного . Сначала напишите используя двоичную кодировку , и пусть . Поверните средние биты, перемешайте правые биты. Игнорирование битов, вращение средних битов и перетасовывание правых n n = 2 k 0 + ⋯ + 2 k w n n i = 2 $n=2^k$$n$$n = 2^{k_0} + \cdots + 2^{k_w}$$n$ n$n_i = 2^{k_i} + \cdots + 2^{k_w}$$n_0$ 2 k 0 n 1 2 k 1 O ( n 0 + ⋯ + n w ) = O ( n ) n t + $2^{k_0}$$2^{k_0}$$n_1$$2^{k_1}$биты. И так далее. Обратите внимание, что вращение легко, поскольку первые несколько вращающихся элементов функционируют как лидеры цикла. Общая сложность вращения составляет , поскольку . Общая сложность внутренних перемешиваний составляет .$O(n_0 + \cdots + n_w) = O(n)$O ( 2 k 0 + ⋯ + 2 k w ) = O ( n $n_{t+1} < n_t/2$$O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$

Осталось показать, как вычислить идеальный случайный порядок при . Фактически, мы сможем определить лидеров цикла, следуя классической работе над ожерельями (Фредриксен и Майорана, Ожерелья из бисера в цветах и хари де Брюйна ; Фредриксен и Кесслер, Алгоритм генерации ожерелий из бисера в двух цветах ).k k$n=2^k$$k$$k$

Какая связь? Я утверждаю, что случайная перестановка соответствует сдвигу вправо двоичного представления. Вот подтверждение для : Поэтому, чтобы найти лидеров цикла, нам нужно найти одного представителя из каждого класса эквивалентности вращения двоичных строк длины . Упомянутые выше документы дают следующий алгоритм генерации всех лидеров цикла. Начните с . На каждом этапе мы находимся в некоторой точке . Найти максимальный индекс нулевого бита,000 001 010 011 100 101 110 111 000 100 001 101 010 110 011 111$n=8$

$$\begin{array}{cccccccc} 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 000 & 100 & 001 & 101 & 010 & 110 & 011 & 111 \end{array}$$ $k$a 1 … a k$0^k$$a_1 \ldots a_k$$i$$k$по чтобы получить , и пусть следующая точка будет . Всякий раз, когда , новая строка является лидером цикла.$i$$k = d\cdot i + r$$(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$$r = 0$

Например, когда генерируется последовательность 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111 , 1111$n=16$

$$\mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011}, \mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}.$$

Лидеры цикла выделены.

Это был начальный вопрос на cs.stackexchange.com, и ответ здесь: /cs/332/in-place-algorithm-for-interleaving-an-array/400#400

Это объяснение статьи: http://arxiv.org/abs/0805.1598 .

$k$$2$$k$$3^2$$k=2$

Обратите внимание, что этот ответ имеет дело с перестановкой (т.е. Inshuffle), и наличие этого также облегчает решение этой проблемы (Outshuffle).$j \to 2j \mod 2n+1$

Что произойдет, если вы запишете риффл шаффл как функцию? Если - длина всего массива, пусть - длина массива после удаления первого и последнего элемента. Тогда перетасованный индекс индекса имеет вид если и если . Затем вы можете просто «перескочить указатель» через массив, меняя местами повторное применение функции.п = т - 2 я е ( я ) = 2 ⋅ я я ≤ п / 2 е ( я ) = 2 ⋅ ( $m$$n = m-2$$i$$f(i) = 2\cdot i$$i \leq n/2$i > n /$f(i) = 2 \cdot (i \mod n/2) - 1$$i > n/2$

Предполагая произвольный доступ, это будет линейное время, требующее дополнительных слов (для хранения значения массива при любом заданном индексе) и, таким образом, дополнительного пространства.O ( log n $O(1)$$O(\log n)$