Heap's algorithm是由B. R. Heap於1963年提出的一種生成全排列的算法。Robert Sedgewick 在1977年的文章中評價該算法是當時最有效的全排列生成算法。該算法旨在使用儘量少的移動數來生成排列。給定一個當前排列，該算法只需從當前排列交換一對元素來產生下一個排列。
基本介紹
- 外文名：Heap's algorithm
- 提出者：B. R. Heap
- 提出時間：1963年
- 性質：算法
相關背景,算法描述,算法偽代碼,正確性證明,
相關背景
Heap's algorithm是一種生成全排列的算法。該算法由B. R. Heap於1963年提出。Robert Sedgewick在1977年的文章中評價該算法是當時最有效的全排列生成算法。
該算法旨在使用儘量少的移動數來生成排列。給定一個當前排列，該算法只需從當前排列交換一對元素來產生下一個排列。
算法描述
Heap's algorithm遞歸的產生n個不同物品的全排列。具體來說，首先因為有n個物品，我們用1至n將這些物品編號。我們執行下列步驟：
(1) 我們設定一個變數i，初始化i為0。
(2) i等於n則算法產生所有全排列，退出。i不等於n，執行第(3)步。
(3) 我們用該算法產生了前n-1個物品的全排列 (共(n-1)!個)。我們將第n個物品作為最後一個元素放入到這些排列中。這樣，我們就得到了所有n個不同物品的全排列中，第n個物品在排列的最後一位的排列。接下來，如果n是奇數，則我們將排列里的第一個元素與最後一個元素互換。如果n是偶數，我們將排列的第i個元素與最後一個元素互換。
(4) i加1。回第(2)步。
算法偽代碼
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n - 1; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
else
swap(A[0], A[n-1])
end if
end for
generate(n - 1, A)
end if
非遞歸的偽代碼可見。
正確性證明
歸納法證明算法的正確性見。
