概要
本記事では、順列生成アルゴリズムであるHeapアルゴリズムをPythonを用いて実装します。競技プログラミングや、業務で順列生成をPythonで行う場合、通常Pythonのitertoolsモジュールを使用するのが効率的ですが、アルゴリズムの仕組みを理解するため、あえてitertoolsを使用せずにHeapアルゴリズムを自力で実装してみます。
Heapアルゴリズムの動作原理
本アルゴリズムの基本的な動作は以下の通りです。：
- 配列のサイズが1の場合、現在の配列を出力（順列として確定）
- サイズが2以上の場合：
・部分配列の順列を生成
・偶数サイズなら現在のインデックスiと最後の要素をスワップ
・奇数サイズなら最初の要素と最後の要素をスワップ
実装例では、再帰を用いて行います。
実装
def heap_permutation(data, size):
if size == 1:
print(data) # 現在の順列を出力
for i in range(size):
# 再帰呼び出し
heap_permutation(data, size - 1)
# 偶数サイズの場合: インデックスiと最後の要素を交換
if size % 2 == 0:
data[i], data[size - 1] = data[size - 1], data[i]
# 奇数サイズの場合: 最初の要素と最後の要素を交換
else:
data[0], data[size - 1] = data[size - 1], data[0]
elements = [1, 2, 3]
heap_permutation(elements, len(elements))
出力結果
上記のアルゴリズムを実装した結果は以下のようになります。
[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]
この再帰関数の動きが分かりづらかったので、間にコメントを入れてみました。その結果以下の様になりました。
heap_permutationが呼び出されました: data=[1, 2, 3], size=3
=== ループ開始 (data=[1, 2, 3], size=3) ===
現在のループ状態: i=0, size=3, data=[1, 2, 3]
heap_permutationが呼び出されました: data=[1, 2, 3], size=2
=== ループ開始 (data=[1, 2, 3], size=2) ===
現在のループ状態: i=0, size=2, data=[1, 2, 3]
heap_permutationが呼び出されました: data=[1, 2, 3], size=1
出力される順列: [1, 2, 3]
スワップ（サイズが偶数: size=2）: data[0] <-> data[1], 結果のdata=[2, 1, 3]
=== ループ終了 ===
=== ループ開始 (data=[2, 1, 3], size=2) ===
現在のループ状態: i=1, size=2, data=[2, 1, 3]
heap_permutationが呼び出されました: data=[2, 1, 3], size=1
出力される順列: [2, 1, 3]
スワップ（サイズが偶数: size=2）: data[1] <-> data[1], 結果のdata=[2, 1, 3]
=== ループ終了 ===
スワップ（サイズが奇数: size=3）: data[0] <-> data[2], 結果のdata=[3, 1, 2]
=== ループ終了 ===
=== ループ開始 (data=[3, 1, 2], size=3) ===
現在のループ状態: i=1, size=3, data=[3, 1, 2]
heap_permutationが呼び出されました: data=[3, 1, 2], size=2
=== ループ開始 (data=[3, 1, 2], size=2) ===
現在のループ状態: i=0, size=2, data=[3, 1, 2]
heap_permutationが呼び出されました: data=[3, 1, 2], size=1
出力される順列: [3, 1, 2]
スワップ（サイズが偶数: size=2）: data[0] <-> data[1], 結果のdata=[1, 3, 2]
=== ループ終了 ===
=== ループ開始 (data=[1, 3, 2], size=2) ===
現在のループ状態: i=1, size=2, data=[1, 3, 2]
heap_permutationが呼び出されました: data=[1, 3, 2], size=1
出力される順列: [1, 3, 2]
スワップ（サイズが偶数: size=2）: data[1] <-> data[1], 結果のdata=[1, 3, 2]
=== ループ終了 ===
スワップ（サイズが奇数: size=3）: data[0] <-> data[2], 結果のdata=[2, 3, 1]
=== ループ終了 ===
=== ループ開始 (data=[2, 3, 1], size=3) ===
現在のループ状態: i=2, size=3, data=[2, 3, 1]
heap_permutationが呼び出されました: data=[2, 3, 1], size=2
=== ループ開始 (data=[2, 3, 1], size=2) ===
現在のループ状態: i=0, size=2, data=[2, 3, 1]
heap_permutationが呼び出されました: data=[2, 3, 1], size=1
出力される順列: [2, 3, 1]
スワップ（サイズが偶数: size=2）: data[0] <-> data[1], 結果のdata=[3, 2, 1]
=== ループ終了 ===
=== ループ開始 (data=[3, 2, 1], size=2) ===
現在のループ状態: i=1, size=2, data=[3, 2, 1]
heap_permutationが呼び出されました: data=[3, 2, 1], size=1
出力される順列: [3, 2, 1]
スワップ（サイズが偶数: size=2）: data[1] <-> data[1], 結果のdata=[3, 2, 1]
=== ループ終了 ===
スワップ（サイズが奇数: size=3）: data[0] <-> data[2], 結果のdata=[1, 2, 3]
=== ループ終了 ===
この結果は、個人的にめちゃくちゃわかりやすかったので共有します。
最後に
参考にあるWikipediaのページでは、再帰を用いない実装例も掲載されているが、自力で実装できるほど理解できていないので掲載しません...
参考