順列PをSwiftで書いただけの記事 その2

はじめに

以前、順列PをSwiftで書いただけの記事を書きました。
順列とは、「1から4の数字が書いた4枚のカードの並べ方はいくつありますか（また、その並べ方は何か）」という問題で出てくるやつです。1, 3, 2, 4 や 2, 4, 3, 1 が順列。

前に書いたこの記事では要素数を指定したら全部を一気に返す仕様でした。例えば要素数が6なら720個返ってきます。

しかし、現在の状態から次のものへ変換する関数も需要があるのではと思い、（すでに存在すると思うが興味があって）作成しました。
次のものってなんだ、ということですが、
[1, 2, 3, 4]の次は[1, 2, 4, 3]
その次は[1, 3, 2, 4]
その次は[1, 3, 4, 2]
となります。
[1, 2, 3, 4]の状態でこの関数を実行すると[1, 2, 4, 3]に変わります。

仕様

124653から125346にするには

1.配列の後ろから見ていって下がったところを見つける

下がったところ（のインデックス）をkeyとする

2.keyより右をひっくり返す

3.keyより右を順番に見て、keyより大のものを見つける。それをkeyの値と交換する。

4. 完成

実装

inoutで渡しているので関数内で書き換えます。
次がある場合はtrueを返します。次がない場合はfalseを返します
初めの状態は 1, 2, 3, 4 のような昇順

import Foundation

func nextPermu(_ a: inout [Int]) -> Bool {

    guard a.count >= 2 else {
        return false //nextは存在しない
    }

    let last = a.count - 1
    
    //find key place
    var key = -1
    var right = a[last]
    for i in (0..<last).reversed() {
        if a[i] < right {
            key = i
            break
        }
        right = a[i]
    }
    guard key != -1 else {
        return false
    }
    
    /* 例 123654のとき
     last 5
     key 2
     順番交換範囲 3個
     順番交換インデックス 3から5
     */
    
    //keyより右をひっくり返す
    let turn = last - key //交換範囲
    /* 例
     turn1 交換作業なし
     turn2 交換作業1回
     turn3 交換作業1回（真ん中は必要なし）
     turn4 交換作業2回
     */
    
    for i in 0..<turn / 2 {
        let temp = a[last - i]
        a[last - i] = a[key + 1 + i]
        a[key + 1 + i] = temp
    }
    
    //keyより右で、初めにあるkeyより大きいものをkeyと交換
    for i in 1...last - key {
        if a[key + i] > a[key] {
            let temp = a[key]
            a[key] = a[key + i]
            a[key + i] = temp
            break
        }
    }
    return true
}

var a = [1, 2, 3, 4, 5, 6]

while nextPermu(&a) {
    print(a)
}