概要

　本記事では、順列生成アルゴリズムである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のページでは、再帰を用いない実装例も掲載されているが、自力で実装できるほど理解できていないので掲載しません...

参考