順列の生成アルゴリズム（Heapアルゴリズム）

# 概要
　本記事では、順列生成アルゴリズムである**Heapアルゴリズム**をPythonを用いて実装します。競技プログラミングや、業務で順列生成をPythonで行う場合、通常Pythonのitertoolsモジュールを使用するのが効率的ですが、アルゴリズムの仕組みを理解するため、あえてitertoolsを使用せずにHeapアルゴリズムを自力で実装してみます。

# Heapアルゴリズムの動作原理
　本アルゴリズムの基本的な動作は以下の通りです。：
1. 配列のサイズが1の場合、現在の配列を出力（順列として確定）
1. サイズが2以上の場合：
    ・部分配列の順列を生成
    ・偶数サイズなら<INS>**現在のインデックスi**</INS>と最後の要素をスワップ
    ・奇数サイズなら<INS>**最初の要素**</INS>と最後の要素をスワップ

実装例では、再帰を用いて行います。

# 実装
```Python
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のページでは、再帰を用いない実装例も掲載されているが、自力で実装できるほど理解できていないので掲載しません...
 
# 参考

https://ja.wikipedia.org/wiki/Heap%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0