[Swift] 順列を列挙する関数

https://qiita.com/kei_tnk/items/246b502200ee7cfb6ac2

↑ こちらの @kei_tnk さんの記事を読んで、「[Heapのアルゴリズム](https://ja.wikipedia.org/wiki/Heapのアルゴリズム)」を知りました。
_（ Heapさんのアルゴリズム ）_

<br>これまで、

# C++標準ライブラリ`next_permutation`ライクな関数
「順列を列挙するアルゴリム」としては、C++の標準ライブラリで提供されている[`next_permutation`](https://cpprefjp.github.io/reference/algorithm/next_permutation.html)のアルゴリズムを真似た、次のコードを使っていました。

```swift:#0 next_permutation ライクな関数
@inlinable public
func nextPermutation<T: Comparable>(_ array: inout [T]) -> Bool {
    guard array.count > 1 else { return false }
    var i = array.count - 1
    while i > 0 && array[i - 1] >= array[i] { i -= 1 }
    if i <= 0 {
        array.reverse()
        return false
    }
    var j = array.count - 1
    while array[i - 1] >= array[j] { j -= 1 }
    array.swapAt(i - 1, j)
    array[i...].reverse()
    return true
}
```

↑ この関数は、「ソート済み」配列が前提で、配列内の要素間の比較や置換、部分ソートによって、重複が自動的に排除されるアルゴリズムとなっています。呼ばれる度に、「次の順列」を生成する関数のため、結果セットを一括で返す関数とは異なり、性能は良い方です。
使い方は、（C++の`next_permutation`と同様に）後判定ループになります。

```swift:nextPermutation(_:)使い方
//ソート済み配列、要素はComparable準拠型（Int, String, Character, 他）
var A = Array("zzyyxaabbcc").sorted()
var count = 0
repeat {
    //Aを処理
    count += 1
} while nextPermutation(&A)
print(count) //1247400（重複排除後）
```

<br><br>一方、Heapさんのアルゴリズムは、


# Heapのアルゴリズムによる実装

https://ja.wikipedia.org/wiki/Heapのアルゴリズム

[<img width="500" alt="code1.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/283293/923fc832-1896-c362-c54b-0c88752b51d2.png" />](https://ja.wikipedia.org/wiki/Heapのアルゴリズム)


Wikipedia での疑似コードは、「再帰処理版」と「（非再帰）ループ処理版」の二つが紹介されている。どちらもアルゴリズムは同じで、実装方法として、再帰と非再帰がある ということです。
この関数の特徴は、入力の配列は（配列内の要素間の比較が無いため）ソート済みである必要はなく、一度の関数呼び出しですべての結果を作りだすようになっている。このため、重複排除は別で行う必要がある

疑似コードの`output(A)`の実装方法で、次の3通りが考えられる。

1. 結果セットを保持する配列を用意して、`output(A)`の箇所で`A`を結果セットに追加し、結果セット全体を返す
2. 結果セットを保持する配列は用意せず、`output(A)`の箇所で、現在の`A`を引数としてコールバック関数を呼び出す
3. Swiftのイテレータインタフェースとして実装する

#3は、#2のインタフェース違いの実装で、実質は、結果セットを作るか作らないかの 2通りです。

- #1と#2は 再帰と非再帰のどちらでも実現できるが、#3は 非再帰のみで実現可能

- #1は 結果セットを使った重複排除を関数側で行うことができるが、
#2と#3は 結果セットを持たないため、重複の排除は 呼び出し側で行う必要がある

## Heapのアルゴリズムの実装例

（冒頭の @kei_tnk さんの記事で紹介されたコードをベースに改変）

```swift:#1-1 再帰処理版
@inlinable public
func permutation1<T>(_ ary: [T]) -> Set<[T]> {
    let N = ary.count
    var A = ary
    var result = [[T]]()

    func rec(_ n: Int) {
        if n == 1 {
            result.append(A)
        } else {
            for i in 0 ..< n {
                rec(n - 1)
                if i.isMultiple(of: 2) {
                    A.swapAt(i, n - 1)
                } else {
                    A.swapAt(0, n - 1)
                }
            }
        }
    }

    rec(N)
    return Set(result)
}

//使い方
let A = Array("zzyyxaabbcc")
var cnt = 0
for a in permutation1(A) {
    //aを処理
    cnt += 1
}
print(cnt) //1247400（重複排除後）
```

```swift:#1-2 （非再帰）ループ処理版
@inlinable public
func permutation1_2<T>(_ ary: [T]) -> Set<[T]> {
    let N = ary.count
    var A = ary
    var result = [[T]]()
    var C = [Int](repeating: 0, count: N)
    var i = 0

    result.append(A)

    while i < N {
        if C[i] < i {
            if i.isMultiple(of: 2) {
                A.swapAt(0, i)
            } else {
                A.swapAt(C[i], i)
            }

            result.append(A)

            C[i] += 1
            i = 0

        } else {
            C[i] = 0
            i += 1
        }
    }
    return Set(result)
}

//使い方
let A = Array("zzyyxaabbcc")
var cnt = 0
for a in permutation1_2(A) {
    //aを処理
    cnt += 1
}
print(cnt) //1247400（重複排除後）
```

```swift:#2 コールバック方式（非再帰ループ処理版）
@inlinable public
func permutation2<T>(_ ary: inout [T], _ callback: ((inout [T])->Void)) {
    let N = ary.count
    var c = [Int](repeating: 0, count: N)
    var i = 0

    callback(&ary)

    while i < N {
        if c[i] < i {
            if i.isMultiple(of: 2) {
                ary.swapAt(0, i)
            } else {
                ary.swapAt(c[i], i)
            }

            callback(&ary)

            c[i] += 1
            i = 0

        } else {
            c[i] = 0
            i += 1
        }
    }
}

//使い方
var A = Array("zzyyxaabbcc")
var cnt = 0
permutation2(&A) { x in
    //xを処理
    cnt += 1
}
print(cnt) //39916800（重複含む）
```

（#2-1 コールバック方式（再帰処理版）は省略）


```swift:#3 イテレータインタフェース版
@inlinable public
struct permutation3<Element>: Sequence, IteratorProtocol, Sendable where Element: Sendable  {
    @usableFromInline
    internal var array: [Element]
    @usableFromInline
    internal var counting: [Int]
    @usableFromInline
    internal var index = 0
    @usableFromInline
    internal var first = true
    @usableFromInline
    internal var reachedEnd = false
    init(_ elements: [Element]) {
        array = elements
        counting = [Int](repeating: 0, count: array.count)
        if array.count == 0 { reachedEnd = true }
    }
    @inlinable
    public mutating func next() -> [Element]? {
        if reachedEnd { return nil }
        if first {
            first = false
            return array
        } else {
            while index < array.count {
                if counting[index] < index {
                    if index.isMultiple(of: 2) {
                        array.swapAt(0, index)
                    } else {
                        array.swapAt(counting[index], index)
                    }
                    counting[index] += 1
                    index = 0
                    return array

                } else {
                    counting[index] = 0
                    index += 1
                }
            }
            return nil
        }
    }
}

//使い方
let A = Array("zzyyxaabbcc")
var cnt = 0
for a in permutation3(A) {
    //aを処理
    cnt += 1
}
print(cnt) //39916800（重複含む）
```





# アルゴリズムによる特徴、性能

特徴を表にまとめます。

|	#	|	アルゴリズム	|	入力配列ソート	|	結果セット	|	配列内要素比較	|	配列内要素置換	|	配列内部分ソート	|	重複排除	|
|	:-:	|	:-	|	:-:	|	:-:	|	:-:	|	:-:	|	:-:	|	:-:	|
|	0	|	C++ next_permutation 相当	|	必要	|	なし	|	あり	|	あり	|	あり	|	あり	|
|	1-1	|	Heapアルゴリズム（再帰処理）	|	不要	|	あり	|	なし	|	あり	|	なし	|	可	|
|	1-2	|	Heapアルゴリズム（（非再帰）ループ処理）	|	不要	|	あり	|	なし	|	あり	|	なし	|	可	|
|	2	|	Heapアルゴリズム（コールバック版）	|	不要	|	なし	|	なし	|	あり	|	なし	|	不可（呼び出し側で可）	|
|	3	|	Heapアルゴリズム（イテレータ版）	|	不要	|	なし	|	なし	|	あり	|	なし	|	不可（呼び出し側で可）	|

自分のPCでの測定値（アルゴリズム間の比較としての参考値）

　重複なし要素数11 = 全列挙数 = 39,916,800（約40千万通り）
　重複あり要素数11 = 全列挙 - 重複 = 1,247,400（約120万通り）
 

|	#	|	アルゴリズム	|	重複なし要素数11	|	重複あり要素数11	|
|	:-:	|	:-	|	:-:	|	:-:	|
|	0	|	C++ next_permutation 相当<br>`nextPermutation`	|	38秒	|	_1.5秒_	|
|	1-1	|	Heapアルゴリズム（再帰処理）<br>`permutation1`	|	140秒	|	74秒	|
|	1-2	|	Heapアルゴリズム（非再帰ループ処理）<br>`permutation1_2`	|	101秒	|	42秒	|
|	2	|	Heapアルゴリズム（コールバック）<br>`permutation2`	|	_10秒_	|	-	|
|	3	|	Heapアルゴリズム（イテレータ）<br>`permutation3`	|	12秒	|	-	|
|	4	|	Apple謹製 Swift-Algorythms<br>[`permutations`](https://swiftpackageindex.com/apple/swift-algorithms/1.2.0/documentation/algorithms/swift/collection/permutations(ofcount:)-7rc99)	|	124秒	|	-	|
|	5	|	Apple謹製 Swift-Algorythms<br>[`uniquePermutations`](https://swiftpackageindex.com/apple/swift-algorithms/1.2.0/documentation/algorithms/swift/collection/uniquepermutations(ofcount:)-2extq)	|	-	|	4秒	|


重複のない配列の場合は、Heapアルゴリズムの方が速い。中でも、（結果セットを作らない）非再帰ループ処理で実装したコールバック方式`permutation2`が最速。
重複あり配列の場合は、`nextPermutation`が1桁速い。

:::note
[`Swift-Algorythms`](https://swiftpackageindex.com/apple/swift-algorithms)で公開されている`permutations`,`uniquePermutations`よりも高速
:::

# 結論

自分の結論ですが、重複のあり/なしで`nextPermutation`と`permutation2`を使い分けしようと思います。

# 参考

- ABC363-C 解説 から抜粋

[![順列を列挙するアルゴリム.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/283293/c05f1a00-2737-edf3-13f5-9b5b88936b3b.png)](https://atcoder.jp/contests/abc363/editorial/10481)

↑ `next_permutation`のアルゴリズムです<br>　


- GNU C++ 標準ライブラリ`next_permutation`ソースコード


https://github.com/gcc-mirror/gcc/blob/63663e4e69527b308687c63bacb0cc038b386593/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2883

**以上**