Алгоритм Хипа

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

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

Подробности алгоритма

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

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

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        // Generate permutations with k-th unaltered
        // Initially k = length(A)
        generate(k - 1, A)

        // Generate permutations for k-th swapped with each k-1 initial
        for i := 0; i < k-1; i += 1 do
            // Swap choice dependent on parity of k (even or odd)
            if k is even then
                swap(A[i], A[k-1]) // zero-indexed, the k-th is at k-1
            else
                swap(A[0], A[k-1])
            end if
            generate(k - 1, A)
        end for
    end if

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

procedure generate(n : integer, A : array of any):
    // c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k - 1, A) is called
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)
    
    // i acts similarly to a stack pointer
    i := 1;
    while i < n do
        if  c[i] < i then
            if i is even then
                swap(A[0], A[i])
            else
                swap(A[c[i]], A[i])
            end if
            output(A)
            // Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
            c[i] += 1
            // Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
            i := 1
        else
            // Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
            c[i] := 0
            i += 1
        end if
    end while

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

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

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        for i := 0; i < k; i += 1 do
            generate(k - 1, A)
            if k is even then
                swap(A[i], A[k-1])
            else
                swap(A[0], A[k-1])
            end if

        end for
    end if

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

Основание: Приведенное выше утверждение тривиально справедливо для $n=1$ поскольку алгоритм Хипа просто вернет $A$ без изменений по порядку.

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

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

1,2,3,4 ... Original Array
1,2,3,4 ... 1st iteration (Permute subset)
4,2,3,1 ... 1st iteration (Swap 1st element into "buffer")
4,2,3,1 ... 2nd iteration (Permute subset)
4,1,3,2 ... 2nd iteration (Swap 2nd element into "buffer")
4,1,3,2 ... 3rd iteration (Permute subset)
4,1,2,3 ... 3rd iteration (Swap 3rd element into "buffer")
4,1,2,3 ... 4th iteration (Permute subset)
4,1,2,3 ... 4th iteration (Swap 4th element into "buffer") ... The altered array is a rotated version of the original

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

1,2,3,4,5 ... Original Array
4,1,2,3,5 ... 1st iteration (Permute subset/Rotate subset)
5,1,2,3,4 ... 1st iteration (Swap)
3,5,1,2,4 ... 2nd iteration (Permute subset/Rotate subset)
4,5,1,2,3 ... 2nd iteration (Swap)
2,4,5,1,3 ... 3rd iteration (Permute subset/Rotate subset)
3,4,5,1,2 ... 3rd iteration (Swap)
1,3,4,5,2 ... 4th iteration (Permute subset/Rotate subset)
2,3,4,5,1 ... 4th iteration (Swap)
5,2,3,4,1 ... 5th iteration (Permute subset/Rotate subset)
1,2,3,4,5 ... 5th iteration (Swap) ... The final state of the array is in the same order as the original

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

Основа: Алгоритм Хипа тривиально переставляет массив $A$ размера $1,$ поскольку вывод $A$ является единственной перестановкой $A$ .

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

Частые неправильные реализации

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

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else

        // Recursively call once for each k
        for i := 0; i < k; i += 1 do
            generate(k - 1, A)
            // swap choice dependent on parity of k (even or odd)
            if k is even then
                // no-op when i == k-1
                swap(A[i], A[k-1])
            else
                // XXX incorrect additional swap when i==k-1
                swap(A[0], A[k-1]) 
            end if

        end for
    end if

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

$n$	$n!-1$	свопы	дополнительно = свопы $-(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

Эти дополнительные замены существенно меняют порядок $k-1$ префиксные элементы.

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

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else

        // Recursively call once for each k
        for i := 0; i < k; i += 1 do
            generate(k - 1, A)
            // avoid swap when i==k-1
            if (i < k - 1)
                // swap choice dependent on parity of k
                if k is even then
                    swap(A[i], A[k-1])
                else
                    swap(A[0], A[k-1])
                end if
            end if
        end for
    end if

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

См. также

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

Ссылки

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

[Heap-1] Хип, БР (1963). «Перестановки путем обмена» . Компьютерный журнал . 6 (3): 293–4. дои : 10.1093/comjnl/6.3.293 .

[2] Седжвик, Р. (1977). «Методы генерации перестановок» . Обзоры вычислительной техники ACM . 9 (2): 137–164. дои : 10.1145/356689.356692 . S2CID 12139332 .

[3] Седжвик, Роберт (4 июня 2020 г.). «Доклад об алгоритмах генерации перестановок» (PDF) .

[ 1 ]

[ 2 ]

[ 3 ]