Алгоритм кучи - Heaps algorithm - Wikipedia

Не путать с heapsort.

Карта 24 перестановок и 23 перестановок, используемых в алгоритме Кучи, переставляющая четыре буквы A (янтарный), B (синий), C (голубой) и D (темно-красный)

Колесная диаграмма всех перестановок длины ${\displaystyle n=4}$ генерируется алгоритмом Heap, где каждая перестановка имеет цветовую кодировку (1 = синий, 2 = зеленый, 3 = желтый, 4 = красный).

Куча алгоритм генерирует все возможные перестановки из п объекты. Впервые он был предложен Б. Р. Хипом в 1963 г.^[1] Алгоритм минимизирует перемещение: он генерирует каждую перестановку из предыдущей, меняя местами одну пару элементов; другой п−2 элементы не нарушены. В обзоре алгоритмов генерации перестановок 1977 г. Роберт Седжвик пришел к выводу, что это был самый эффективный алгоритм для генерации перестановок на компьютере.^[2]

В последовательность перестановок п объекты, генерируемые алгоритмом Хипа, являются началом последовательности перестановок п+1 объекты. Итак, есть одна бесконечная последовательность перестановок, сгенерированная алгоритмом Хипа (последовательность A280318 в OEIS ).

Детали алгоритма

Для коллекции ${\displaystyle C}$ содержащий п различных элементов, Хип нашел систематический метод выбора на каждом шаге пары элементов для переключения, чтобы произвести каждую возможную перестановку этих элементов ровно один раз.

Рекурсивно описывается как уменьшаться и побеждать метод, алгоритм Heap работает на каждом шаге ${\displaystyle k}$ начальные элементы коллекции. Первоначально ${\displaystyle k==n}$ и после этого ${\displaystyle k<n}$. Каждый шаг генерирует ${\displaystyle k!}$ перестановки, которые заканчиваются тем же ${\displaystyle n-k}$ заключительные элементы. Он делает это, вызывая себя один раз с ${\displaystyle k{\text{th}}}$ элемент без изменений, а затем ${\displaystyle k-1}$ раз с (${\displaystyle k{\text{th}}}$) элемент обменивается на каждый из ${\displaystyle k-1}$ элементы. Рекурсивные вызовы изменяют начальный ${\displaystyle k-1}$ На каждой итерации требуется правило, чтобы выбрать, какие элементы будут заменены последними. Метод кучи говорит, что этот выбор может быть сделан паритет количества элементов, задействованных на этом этапе. Если ${\displaystyle k}$ четно, то последний элемент итеративно обменивается с каждым индексом элемента. Если ${\displaystyle k}$ нечетный, последний элемент всегда заменяется первым.

процедура генерировать(k : целое число, А : множество из любой):    если k = 1 тогда        выход(А)    еще        // Генерируем перестановки с неизмененным k-м        // Изначально k == length (A)        генерировать(k - 1, А)        // Генерируем перестановки для k-го, поменяв местами каждый начальный k-1        за я := 0; я < k-1; я += 1 делать            // Выбор обмена зависит от четности k (четное или нечетное)            если k является четное тогда                замена(А[я], А[k-1]) // с нулевым индексом, k-й находится в k-1            еще                замена(А[0], А[k-1])            конец если            генерировать(k - 1, А)        конец за    конец если

Также можно написать алгоритм в нерекурсивном формате.^[3]

процедура генерировать(п : целое число, А : множество из любой):    // c - это кодировка состояния стека. c [k] кодирует счетчик цикла for, когда вызывается generate (k - 1, A)    c : множество из int    за я := 0; я < п; я += 1 делать        c[я] := 0    конец за    выход(А)        // i действует аналогично указателю стека    я := 0;    пока я < п делать        если  c[я] < я тогда            если я является четное тогда                замена(А[0], А[я])            еще                замена(А[c[я]], А[я])            конец если            выход(А)            // Произошел своп, завершающий цикл for. Моделируйте приращение счетчика цикла            c[я] += 1            // Имитировать рекурсивный вызов, достигающий базового случая, переводя указатель на аналог базового случая в массиве            я := 0        еще            // Вызов метода generate (i + 1, A) завершился, так как цикл for завершился. Сбросьте состояние и имитируйте выталкивание стека, увеличивая указатель.            c[я] := 0            я += 1        конец если    конец пока

Доказательство

В этом доказательстве мы будем использовать реализацию ниже как алгоритм кучи. Хотя это не оптимально (см. Раздел ниже)^{[требуется разъяснение ]}, реализация тем не менее верна и произведет все перестановки. Причина использования приведенной ниже реализации заключается в том, что анализ проще, и определенные закономерности можно легко проиллюстрировать.

процедура генерировать(k : целое число, А : множество из любой):    если k = 1 тогда        выход(А)    еще        за я := 0; я < k; я += 1 делать            генерировать(k - 1, А)            если k является четное тогда                замена(А[я], А[k-1])            еще                замена(А[0], А[k-1])             конец если        конец за    конец если

Утверждение: если массив А имеет длину п, то выполнение алгоритма кучи либо приведет к А "повернутый" вправо на 1 (т.е. каждый элемент сдвигается вправо, причем последний элемент занимает первую позицию) или приводит к А без изменений, в зависимости от того, п четное или нечетное соответственно.

Основание: утверждение выше тривиально верно для ${\displaystyle n=1}$ поскольку алгоритм кучи просто вернет А без изменений по порядку.

Индукция: предположим, что утверждение верно для некоторых ${\displaystyle i\geq 1}$. Затем нам нужно будет обработать два случая для ${\displaystyle i+1}$: ${\displaystyle i+1}$ четное или нечетное.

Если для А, ${\displaystyle n=i+1}$ четно, то подмножество первого я элементы останутся неизменными после выполнения алгоритма Кучи на подмассиве, как предполагает гипотеза индукции. Выполнив алгоритм кучи на подмассиве, а затем выполнив операцию подкачки, в k-я итерация цикла for, где ${\displaystyle k\leq i+1}$, то kй элемент в А будет заменен на последнюю позицию А который можно рассматривать как своего рода «буфер». Поменяв местами 1-й и последний элементы, затем поменяв местами 2-й и последний, до тех пор, пока пth и last элементы меняются местами, массив, наконец, будет вращаться. Чтобы проиллюстрировать вышесказанное, посмотрите на корпус ниже ${\displaystyle n=4}$

1,2,3,4 ... Исходный массив 1,2,3,4 ... 1-я итерация (перестановка подмножества) 4,2,3,1 ... 1-я итерация (замена 1-го элемента в "буфер") 4, 2,3,1 ... 2-я итерация (перестановка подмножества) 4,1,3,2 ... 2-я итерация (перестановка 2-го элемента в «буфер») 4,1,3,2 ... 3-я итерация (перестановка подмножества ) 4,1,2,3 ... 3-я итерация (замена 3-го элемента в "буфер") 4,1,2,3 ... 4-я итерация (перестановка подмножества) 4,1,2,3 ... 4-я итерация (Поменять 4-й элемент на «буфер») ... Измененный массив представляет собой повернутую версию исходного

Если для А, ${\displaystyle n=i+1}$ нечетное, то подмножество первого я элементы будут повернуты после выполнения алгоритма кучи на первом я элементы. Обратите внимание, что после 1 итерации цикла for при выполнении алгоритма кучи на А, А повернут вправо на 1. По предположению индукции предполагается, что первый я элементы будут вращаться. После этого поворота первый элемент А будет помещен в буфер, который в сочетании с предыдущей операцией вращения, по сути, выполнит поворот массива. Выполните эту операцию вращения п раз, и массив вернется в исходное состояние. Это показано ниже для случая ${\displaystyle n=5}$.

1,2,3,4,5 ... Исходный массив 4,1,2,3,5 ... 1-я итерация (переставить подмножество / повернуть подмножество) 5,1,2,3,4 ... 1-я итерация (поменять местами ) 3,5,1,2,4 ... 2-я итерация (переставить подмножество / повернуть подмножество) 4,5,1,2,3 ... 2-я итерация (поменять местами) 2,4,5,1,3 .. . 3-я итерация (переставить подмножество / повернуть подмножество) 3,4,5,1,2 ... 3-я итерация (поменять местами) 1,3,4,5,2 ... 4-я итерация (переставить подмножество / повернуть подмножество) 2, 3,4,5,1 ... 4-я итерация (Обмен) 5,2,3,4,1 ... 5-я итерация (Переставить подмножество / Повернуть подмножество) 1,2,3,4,5 ... 5-я итерация (Обмен) ... Окончательное состояние массива находится в том же порядке, что и исходное

Доказательство индукции для утверждения теперь завершено, что теперь приведет к тому, почему алгоритм Хипа создает все перестановки массива А. Еще раз докажем по индукции правильность алгоритма Хипа.

Основа: алгоритм Кучи тривиально переставляет массив А размера 1 как вывод А это единственная перестановка А.

Индукция: предположим, что алгоритм Кучи переставляет массив размера я. Используя результаты предыдущего доказательства, каждый элемент А окажется в «буфере» один раз, когда первый я элементы переставляются. Поскольку перестановки массива могут быть выполнены путем изменения некоторого массива А через удаление элемента Икс из А затем прикрепляя Икс к каждой перестановке измененного массива следует, что алгоритм Кучи переставляет массив размера ${\displaystyle i+1}$, поскольку «буфер» по существу содержит удаленный элемент, прикрепленный к перестановкам подмассивов размера я. Поскольку каждая итерация алгоритма кучи имеет разные элементы А занимая буфер при перестановке подмассивов, каждая перестановка генерируется как каждый элемент А имеет шанс привязать к перестановкам массива А без буферного элемента.

Частые ошибки в реализации

Заманчиво упростить рекурсивную версию, приведенную выше, за счет уменьшения количества рекурсивных вызовов. Например, как:

процедура генерировать(k : целое число, А : множество из любой):    если k = 1 тогда        выход(А)    еще        // Рекурсивно вызываем один раз для каждого k        за я := 0; я < k; я += 1 делать            генерировать(k - 1, А)            // выбор обмена зависит от четности k (четное или нечетное)            если k является четное тогда                // нет операции, когда я == k-1                замена(А[я], А[k-1])            еще                // XXX неверный дополнительный своп при i == k-1                замена(А[0], А[k-1])             конец если        конец за    конец если

Эта реализация преуспеет в создании всех перестановок, но не минимизирует перемещение. Поскольку рекурсивный стеки вызовов раскрутите, это приводит к дополнительным свопам на каждом уровне. Половина из них будет запретные операции из ${\displaystyle A[i]}$ и ${\displaystyle A[k-1]}$ куда ${\displaystyle i==k-1}$ но когда ${\displaystyle k}$ странно, это приводит к дополнительным перестановкам ${\displaystyle kth}$ с ${\displaystyle 0th}$ элемент.

${\displaystyle n}$	${\displaystyle n!-1}$	свопы	дополнительный = свопы ${\displaystyle -(n!-1)}$
1	0	0	0
2	1	1	0
3	5	6	1
4	23	27	4
5	119	140	21
6	719	845	126
7	5039	5922	883
8	40319	47383	7064
9	362879	426456	63577

Эти дополнительные свопы значительно изменяют порядок ${\displaystyle k-1}$ префиксные элементы.

Дополнительных свопов можно избежать, добавив дополнительный рекурсивный вызов перед циклом и зациклив ${\displaystyle k-1}$ раз (как указано выше) или же зацикливание ${\displaystyle k}$ раз и проверяя это ${\displaystyle i}$ меньше чем ${\displaystyle k-1}$ как в:

процедура генерировать(k : целое число, А : множество из любой):    если k = 1 тогда        выход(А)    еще        // Рекурсивно вызываем один раз для каждого k        за я := 0; я < k; я += 1 делать            генерировать(k - 1, А)            // избегаем свопа, когда i == k-1            если (я < k - 1)                // выбор обмена зависит от четности k                если k является четное тогда                    замена(А[я], А[k-1])                еще                    замена(А[0], А[k-1])                конец если            конец если        конец за    конец если

Выбор в первую очередь эстетический, но последний приводит к проверке ценности ${\displaystyle i}$ вдвое чаще.

Смотрите также

• Алгоритм Штейнхауса – Джонсона – Троттера

Рекомендации

1. Хип, Б. Р. (1963). «Перестановки развязками» (PDF). Компьютерный журнал. 6 (3): 293–4. Дои:10.1093 / comjnl / 6.3.293.
2. Седжвик, Р. (1977). «Методы генерации перестановок». Опросы ACM Computing. 9 (2): 137–164. Дои:10.1145/356689.356692.
3. Седжвик, Роберт. "доклад об алгоритмах генерации перестановок" (PDF).