配列の中身を使った順列を生成する関数の自作【競技プログラミング】

# はじめに
- また、c++やpythonで対応してるのに、swiftで対応していない関数があったので、なんとか対応したい。
- 必要性に気付いたのは、[ABC363のc問題](https://atcoder.jp/contests/abc363/tasks/abc363_c)。
- やりたいことは単純で、例えば、要素が3つの配列で、中身が「a,b,c」だったときに、abc,acb,bac,bca,cab,cbaのような順番の配列6つ(=3!)を作るということ。
- そのような配列生成は、計算量を無視すれば無理やり作れそうだけど、計算量を抑えて実現するのは意外と難しそうなので、解くのを諦めた。
- 今回、計算量を抑えた手法([ヒープのアルゴリズム](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))を見つけたので、それを使った実装を行う。

# ヒープのアルゴリズムの実装
- ちなみに、ダイクストラ法の高速化で用いた「ヒープ」(積み重なったもの、という意味)とは全く関係ない。こちらのヒープは人名(B. R. Heap)を指す。
- swiftでコードを書くと次のとおり。なお、wikiのコードでは、ダブりの消去を考慮していないので、戻り値をSetにすることで対応した。
```swift
func pmt_gen<T>(_ ary:[T])->Set<[T]>{
    
    let N = ary.count
    var A = ary
    var ans_nonset = [[T]]()
    rec(N,&A,&ans_nonset)

    return Set(ans_nonset)

    func rec<Ti>(_ n:Int , _ A:inout [Ti],_ ans:inout [[Ti]]){
        if n == 1 { 
            ans.append(A)
            } else {
            for i in 0..<n {
                rec(n-1,&A,&ans)
                if n % 2 == 0 {
                    swap(&A,i,n-1)
                } else {
                    swap(&A,0,n-1)
                }
            }
        }
    }

    func swap<Ti>(_ A:inout [Ti],_ a:Int,_ b:Int){
        let temp = A[a]
        A[a] = A[b]
        A[b] = temp
    }   
    
}

let a = ["z","z","y","y","x"]
let b = pmt_gen(a).map{$0.reduce(""){$0 + $1}}.sorted()

print(b) // ["xyyzz", "xyzyz", "xyzzy", "xzyyz", "xzyzy", "xzzyy", "yxyzz", "yxzyz", "yxzzy", "yyxzz", "yyzxz", "yyzzx", "yzxyz", "yzxzy", "yzyxz", "yzyzx", "yzzxy", "yzzyx", "zxyyz", "zxyzy", "zxzyy", "zyxyz", "zyxzy", "zyyxz", "zyyzx", "zyzxy", "zyzyx", "zzxyy", "zzyxy", "zzyyx"]
print(b.count) // 30
```
- 上記コードは、paizaだとエラーが発生するので注意！！`error: link command failed with exit code 1 (use -v to see invocation)`とのことだけど、よくわからん。
- AtCoderのコードテストや、[mycompiler](https://www.mycompiler.io/ja/new/swift)だと問題なく実行できる。ちなみに、型変数Tが内側の関数ではTi(innerの意味でiにした)にしているのは、「内と外で同じ型変数名を使ったら駄目だぞ！」とmycompilerに怒られたから。現状は、メッセージは出るものの実行できるんだけど、エラーメッセージを見ると、swift6からは駄目っぽいね。`warning: generic parameter 'T' shadows generic parameter from outer scope with the same name; this is an error in Swift 6` 
- このヒープのアルゴリズムの肝は、再帰関数recの部分だと思うけど、やっていることは、[このpdf](https://hermes-ir.lib.hit-u.ac.jp/hermes/ir/re/16410/0100803401.pdf)のp379「2.交換による方法-2.1再帰的方法」に書かれている。Wellのアルゴリズムでも同じように出来るみたいだけど、ヒープのアルゴリズムだけ名前が残っているのは何でだろうね。
:::note info
上記のコードはへっぽこなのでpaizaで動かなかったけど、コメント欄の@nak435さんのコードならスッキリしてて、paizaでも動きます！上記、へっぽこコードは戒めのために、このままにしておきます。
:::

# pmt_genを使って提出する
- ABC363のc問題を解いてみる。コードは公式解説をswift用に変えただけ。
```swift
let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var ss = Array(readLine()!).map{$0.asciiValue!}

var ans = 0

var pmt = pmt_gen(ss)

for s in pmt {
    var ok = true
    for i in 0...(N-K) {
        var flag = true
        for j in 0..<K {
            if s[i+j] != s[i+K-1-j] {flag = false}
        }        
        if(flag) {ok = false}
    }
    if ok {ans += 1}   
}

print(ans)
```
- ACだったけど....1.6秒もかかって、メモリも300M以上消費....ギリギリ過ぎじゃん
- そもそも、最初、pmt_genの返り値を配列にするため、Array(Set(ans))の処理を含めたらTLEが発生したので、その処理を省いたんだよね。SetをArrayにするのも、結構な計算量を使うってことね。

# おわりに
- やっぱり、swiftでコンテストに出る場合、自分で関数を事前に用意して置く必要があると実感したね。
- 夏が終わるまでに4完できるかなぁ