WikiDer > Алгоритм кучи - Википедия

Heaps algorithm - Wikipedia
Карта 24 перестановок и 23 перестановок, используемых в алгоритме Кучи, переставляющая четыре буквы A (янтарный), B (синий), C (голубой) и D (темно-красный)
Колесная диаграмма всех перестановок длины генерируется алгоритмом Heap, где каждая перестановка имеет цветовую кодировку (1 = синий, 2 = зеленый, 3 = желтый, 4 = красный).

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

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

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

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

Рекурсивно описывается как уменьшаться и побеждать метод, алгоритм Heap работает на каждом шаге начальные элементы коллекции. Первоначально и после этого . Каждый шаг генерирует перестановки, которые заканчиваются тем же заключительные элементы. Он делает это, вызывая себя один раз с элемент без изменений, а затем раз с () элемент обменивается на каждый из элементы. Рекурсивные вызовы изменяют начальный На каждой итерации требуется правило, чтобы выбрать, какие элементы будут заменены последними. Метод кучи говорит, что этот выбор может быть сделан паритет количества элементов, задействованных на этом этапе. Если четно, то последний элемент итеративно обменивается с каждым индексом элемента. Если нечетный, последний элемент всегда заменяется первым.

процедура генерировать(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 (т.е. каждый элемент сдвигается вправо, причем последний элемент занимает первую позицию) или приводит к А без изменений, в зависимости от того, п четное или нечетное соответственно.

Основание: утверждение выше тривиально верно для поскольку алгоритм кучи просто вернет А без изменений по порядку.

Индукция: предположим, что утверждение верно для некоторых . Затем нам нужно будет обработать два случая для : четное или нечетное.

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

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-й элемент на «буфер») ... Измененный массив представляет собой повернутую версию исходного

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

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 как вывод А это единственная перестановка А.

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

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

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

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

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

свопыдополнительный = свопы
1000
2110
3561
423274
511914021
6719845126
750395922883
840319473837064
936287942645663577

Эти дополнительные свопы значительно изменяют порядок префиксные элементы.

Дополнительных свопов можно избежать, добавив дополнительный рекурсивный вызов перед циклом и зациклив раз (как указано выше) или же зацикливание раз и проверяя это меньше чем как в:

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

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

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

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

  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).