Haldový algoritmus - Heaps algorithm - Wikipedia

Mapa 24 permutací a 23 swapů použitých v Heapově algoritmu permutujících čtyři písmena A (jantarová), B (modrá), C (azurová) a D (tmavě červená)

Schéma kola všech permutací délky ${ displaystyle n = 4}$ generováno Heapovým algoritmem, kde je každá permutace barevně odlišena (1 = modrá, 2 = zelená, 3 = žlutá, 4 = červená).

Haldy algoritmus generuje vše možné obměny z n předměty. Poprvé to navrhl B. R. Heap v roce 1963.^[1] Algoritmus minimalizuje pohyb: generuje každou permutaci z předchozí výměnou jedné dvojice prvků; jiný n−2 prvky nejsou narušeny. V přehledu algoritmů generujících permutaci z roku 1977 Robert Sedgewick dospěl k závěru, že to byl v té době nejúčinnější algoritmus pro generování permutací pomocí počítače.^[2]

The sekvence permutací z n objekty generované Heapovým algoritmem jsou začátkem sekvence permutací n+1 předměty. Existuje tedy jedna nekonečná posloupnost permutací generovaných Hallovým algoritmem (posloupnost A280318 v OEIS ).

Podrobnosti algoritmu

Pro sbírku ${ displaystyle C}$ obsahující n různé prvky, Heap našel systematickou metodu pro výběr v každém kroku dvojici prvků pro přepnutí, aby se vytvořila každá možná permutace těchto prvků přesně jednou.

Rekurzivně popsáno jako a snížit a dobýt Heapův algoritmus pracuje v každém kroku na ${ displaystyle k}$ počáteční prvky kolekce. Zpočátku ${ displaystyle k == n}$ a poté ${ displaystyle k$. Každý krok generuje ${ displaystyle k!}$ permutace, které končí stejným ${ displaystyle n-k}$ závěrečné prvky. Dělá to tak, že si jednou volá s ${ displaystyle k { text {th}}}$ prvek nezměněn a poté ${ displaystyle k-1}$ krát s (${ displaystyle k { text {th}}}$) prvek vyměněn za každý z počátečních ${ displaystyle k-1}$ elementy. Rekurzivní volání upravují počáteční ${ displaystyle k-1}$ prvky a pravidlo je nutné při každé iteraci vybrat, které budou vyměněny za poslední. Heapova metoda říká, že tuto volbu může provést parita počtu prvků operovaných v tomto kroku. Li ${ displaystyle k}$ je sudé, pak se finální prvek iterativně vymění s každým indexem prvku. Li ${ displaystyle k}$ je lichý, poslední prvek se vždy vymění s prvním.

postup generovat(k : celé číslo, A : pole z žádný):    -li k = 1 pak        výstup(A)    jiný        // Generujte permutace s nezměněným kth        // Zpočátku k == délka (A)        generovat(k - 1, A)        // Generujte permutace pro kth vyměněné s každou iniciálou k-1        pro i := 0; i < k-1; i += 1 dělat            // Zaměnit výběr v závislosti na paritě k (sudý nebo lichý)            -li k je dokonce pak                vyměnit(A[i], A[k-1]) // nula indexována, kth je na k-1            jiný                vyměnit(A[0], A[k-1])            konec -li            generovat(k - 1, A)        konec pro    konec -li

Jeden může také psát algoritmus v nerekurzivním formátu.^[3]

postup generovat(n : celé číslo, A : pole z žádný):    // c je kódování stavu zásobníku. c [k] kóduje čítač pro smyčku, když se volá generování (k - 1, A)    C : pole z int    pro i := 0; i < n; i += 1 dělat        C[i] := 0    konec pro    výstup(A)        // i funguje podobně jako ukazatel zásobníku    i := 0;    zatímco i < n dělat        -li  C[i] < i pak            -li i je dokonce pak                vyměnit(A[0], A[i])            jiný                vyměnit(A[C[i]], A[i])            konec -li            výstup(A)            // Došlo k záměně ukončující smyčku for. Simulujte přírůstek čítače pro smyčku            C[i] += 1            // Simulace rekurzivního volání dosaženého v základním případě přenesením ukazatele na analogový základního případu v poli            i := 0        jiný            // Volání generování (i + 1, A) skončilo ukončením smyčky for. Obnovte stav a simulujte vyskakování zásobníku zvýšením ukazatele.            C[i] := 0            i += 1        konec -li    konec zatímco

Důkaz

V tomto důkazu použijeme níže uvedenou implementaci jako haldy Algorithm. I když to není optimální (viz část níže)^{[je zapotřebí objasnění ]}, implementace je přesto stále správná a vytvoří všechny obměny. Důvodem pro použití níže uvedené implementace je, že analýza je jednodušší a lze snadno ilustrovat určité vzorce.

postup generovat(k : celé číslo, A : pole z žádný):    -li k = 1 pak        výstup(A)    jiný        pro i := 0; i < k; i += 1 dělat            generovat(k - 1, A)            -li k je dokonce pak                vyměnit(A[i], A[k-1])            jiný                vyměnit(A[0], A[k-1])             konec -li        konec pro    konec -li

Nárok: Pokud pole A má délku n, pak provedení Heapova algoritmu bude mít za následek A být „otočen“ doprava o 1 (tj. každý prvek je posunut doprava, přičemž poslední prvek zaujímá první pozici) nebo má za následek A se nezmění, podle toho, zda n je sudé, respektive liché.

Základ: Výše ​​uvedené tvrzení triviálně platí pro ${ displaystyle n = 1}$ protože Heapův algoritmus se jednoduše vrátí A nezměněno v pořádku.

Indukce: Předpokládejme, že nárok pro některé platí ${ displaystyle i geq 1}$. Poté budeme muset vyřídit dva případy ${ displaystyle i + 1}$: ${ displaystyle i + 1}$ je sudé nebo liché.

Pokud, pro A, ${ displaystyle n = i + 1}$ je sudé, pak podmnožina prvního i prvky zůstanou nezměněny po provedení Heapova algoritmu na podskupině, jak předpokládá indukční hypotéza. Provedením haldy algoritmu na podřízeném poli a následným provedením operace výměny v kth iterace smyčky for, kde ${ displaystyle k leq i + 1}$, kth prvek v A bude zaměněn na poslední pozici A což lze považovat za jakýsi „nárazník“. Zaměňováním 1. a posledního prvku, poté zaměňováním 2. a posledního, až do nth a poslední prvky jsou zaměněny, pole nakonec zažije rotaci. Pro ilustraci výše, podívejte se níže na případ ${ displaystyle n = 4}$

1,2,3,4 ... Original Array1,2,3,4 ... 1. iterace (podmnožina Permute) 4,2,3,1 ... 1. iterace (Zaměnit 1. prvek do „bufferu“) 4, 2,3,1 ... 2. iterace (podmnožina permutace) 4,1,3,2 ... 2. iterace (zaměnit druhý prvek za „vyrovnávací paměť“) 4,1,3,2 ... 3. iterace (podmnožina permutace) ) 4,1,2,3 ... 3. iterace (Zaměnit 3. prvek za „vyrovnávací paměť“) 4,1,2,3 ... 4. iterace (podmnožina Permute) 4,1,2,3 ... 4. iterace (Zaměňte 4. prvek za „vyrovnávací paměť“) ... Změněné pole je otočená verze originálu

Pokud, pro A, ${ displaystyle n = i + 1}$ je liché, pak podmnožina prvního i prvky budou otočeny po provedení Heapova algoritmu na prvním i elementy. Všimněte si, že po 1 iteraci smyčky for při provádění Heap's Algorithm on A, A se otočí doprava o 1. Indukční hypotézou se předpokládá, že první i prvky se budou otáčet. Po tomto otočení první prvek A budou vyměněny do vyrovnávací paměti, která v kombinaci s předchozí operací rotace v podstatě provede rotaci na poli. Proveďte tuto rotační operaci n krát a pole se vrátí do původního stavu. To je pro případ ilustrováno níže ${ displaystyle n = 5}$.

1,2,3,4,5 ... Original Array4,1,2,3,5 ... 1. iterace (podmnožina Permute / Rotate podmnožina) 5,1,2,3,4 ... 1. iterace (zaměnit ) 3,5,1,2,4 ... 2. iterace (podmnožina permutace / rotace podmnožiny) 4,5,1,2,3 ... 2. iterace (zaměnit) 2,4,5,1,3 .. 3. iterace (podmnožina Permute / podmnožina Rotace) 3,4,5,1,2 ... 3. iterace (zaměnit) 1,3,4,5,2 ... 4. iterace (podmnožina Permute / rotace podmnožiny) 2, 3,4,5,1 ... 4. iterace (Swap) 5,2,3,4,1 ... 5. iterace (podmnožina Permute / Rotate podmnožina) 1,2,3,4,5 ... 5. iterace (Zaměnit) ... Konečný stav pole je ve stejném pořadí jako originál

Indukční důkaz pro reklamaci je nyní kompletní, což nyní povede k tomu, proč Heapův algoritmus vytváří všechny permutace pole A. Opět dokážeme indukcí správnost Heapova algoritmu.

Základ: Heapův algoritmus triviálně permutuje pole A velikosti 1 jako výstup A je jediná permutace A.

Indukce: Předpokládejme, že Heapův algoritmus permutuje pole velikosti i. S využitím výsledků předchozího důkazu, každý prvek A bude v „bufferu“ jednou, když bude první i prvky jsou permutovány. Protože permutace pole lze provést změnou nějakého pole A odstraněním prvku X z A pak připíná X z každé permutace změněného pole vyplývá, že Heapův algoritmus permutuje pole velikosti ${ displaystyle i + 1}$, protože „vyrovnávací paměť“ v podstatě obsahuje odstraněný prvek, který je přichycen na permutace dílčího pole velikosti i. Protože každá iterace haldy algoritmu má jiný prvek A obsazením vyrovnávací paměti, když je podmnožina permutována, je každá permutace generována jako každý prvek A má šanci být přichycen k permutacím pole A bez prvku vyrovnávací paměti.

Časté nesprávné implementace

Je lákavé zjednodušit rekurzivní verzi uvedenou výše snížením počtu případů rekurzivních volání. Například jako:

postup generovat(k : celé číslo, A : pole z žádný):    -li k = 1 pak        výstup(A)    jiný        // Rekurzivně volejte jednou pro každé k        pro i := 0; i < k; i += 1 dělat            generovat(k - 1, A)            // volba swapu závislá na paritě k (sudá nebo lichá)            -li k je dokonce pak                // no-op když i == k-1                vyměnit(A[i], A[k-1])            jiný                // XXX nesprávný další swap, když i == k-1                vyměnit(A[0], A[k-1])             konec -li        konec pro    konec -li

Tato implementace uspěje při vytváření všech permutací, ale nebude minimalizovat pohyb. Jako rekurzivní zásobníky hovorů uvolnit, to má za následek další swapy na každé úrovni. Polovina z nich bude ne-ops z ${ displaystyle A [i]}$ a ${ displaystyle A [k-1]}$ kde ${ displaystyle i == k-1}$ ale když ${ displaystyle k}$ je zvláštní, má za následek další výměny ${ displaystyle kth}$ s ${ displaystyle 0.}$ živel.

${ displaystyle n}$	${ displaystyle n! -1}$	swapy	additional = vymění ${ 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

Tyto dodatečné swapy významně mění pořadí ${ displaystyle k-1}$ prefixové prvky.

Dalším swapům se lze vyhnout buď přidáním dalšího rekurzivního volání před smyčku a smyčku ${ displaystyle k-1}$ krát (jak je uvedeno výše) nebo opakování ${ displaystyle k}$ krát a zkontroluji to ${ displaystyle i}$ je méně než ${ displaystyle k-1}$ jako v:

postup generovat(k : celé číslo, A : pole z žádný):    -li k = 1 pak        výstup(A)    jiný        // Rekurzivně volejte jednou pro každé k        pro i := 0; i < k; i += 1 dělat            generovat(k - 1, A)            // vyhnout se swapu, když i == k-1            -li (i < k - 1)                // volba swapu závislá na paritě k                -li k je dokonce pak                    vyměnit(A[i], A[k-1])                jiný                    vyměnit(A[0], A[k-1])                konec -li            konec -li        konec pro    konec -li

Volba je primárně estetická, ale výsledkem je kontrola hodnoty ${ displaystyle i}$ dvakrát častěji.

Viz také

• Algoritmus Steinhaus – Johnson – Trotter

Reference