前にnext_permutationの実装で試行錯誤したものの、すっかり忘れてしまっていたので備忘を兼ねて
解いていた問題
解法メモ
- いろいろ参考にしてnext_permutation、prev_permutation相当のものを事前に実装しておいちゃう
- 今回の問題はprev_permutationがあればサクッと解ける
- ↓が事前に準備しておいたnext_permutationと、事後的に準備したprev_permutation
/** * next_permutation * 受け取ったリストの次の順列にarrayを更新する * [1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4] * * コードの参考: https://koboshi-kyopro.hatenablog.com/entry/2021/07/21/193611 * コメントの参考: https://qiita.com/Nikkely/items/0ddca51b3c0e60afbaab */ fun nextPermutation(array: MutableList<Int>): Boolean { // i: array[i] < array[i + 1]を満たすもののうちインデックス最大のものを探す。のでdownToでループ for (i in array.lastIndex - 1 downTo 0) { if (array[i] < array[i + 1]) { // j: 末尾から探索して初めて現れるarray[i]より値が大きい要素のインデックスを探す。 for (j in array.lastIndex downTo i + 1) { if (array[j] > array[i]) { // 見つけた。array[i]とarray[j]を入れ替える val tmp = array[i] array[i] = array[j] array[j] = tmp // i+1以降の要素を昇順に並べ替える // i番目までは入れ替え済みor関係ないので、i+1番目からをtakeLastで取得してソート val tmpArray = array.takeLast(array.size - (i + 1)).sorted() tmpArray.forEachIndexed { index, e -> // tmpArrayのindex == arrayのi+1+indexなので、ソート済みの値で上書きしていく array[i + 1 + index] = e } return true } } } } return false } /** * prev_permutation * 受け取ったリストの前の順列にarrayを更新する * [1, 2, 3, 5, 4] -> [1, 2, 3, 4, 5] * * nextPermutationをベースに不等号、ソート順を修正 * 修正方針の参考：https://qiita.com/HMMNRST/items/26786552a2660735d34f */ fun prevPermutation(array: MutableList<Int>): Boolean { // i: array[i] < array[i + 1]を満たすもののうちインデックス最大のものを探す。のでdownToでループ for (i in array.lastIndex - 1 downTo 0) { if (array[i] > array[i + 1]) { // j: 末尾から探索して初めて現れるarray[i]より値が小さい要素のインデックスを探す。 for (j in array.lastIndex downTo i + 1) { if (array[j] < array[i]) { // 見つけた。array[i]とarray[j]を入れ替える val tmp = array[i] array[i] = array[j] array[j] = tmp // i+1以降の要素を降順に並べ替える // i番目までは入れ替え済みor関係ないので、i+1番目からをtakeLastで取得してソート val tmpArray = array.takeLast(array.size - (i + 1)).sortedDescending() tmpArray.forEachIndexed { index, e -> // tmpArrayのindex == arrayのi+1+indexなので、ソート済みの値で上書きしていく array[i + 1 + index] = e } return true } } } } return false }
処理フローのメモ
ざっくりした流れ
- iを決める
- jを決める
- i,jをswap
- iより後ろをソート
- ↑の流れがベースで次の順列を求めるか前の順列を求めるかで不等号やソート順が逆になる
(とても)汚い概略図
ほぼ自分用です、すみません。でも理解できている人には不要だと思うし、理解が甘ければ実際に書いてみるとイメージアップしやすいかと思うので、大丈夫だと思います（？）
提出した回答
参考
- コードの参考: 競プロ典型 90 問を Kotlin で解く - little star's memory
- 実装のベースにさせていただいた
- コメントの参考: next_permutationがイマイチよくわからなかったのでまとめてみた - Qiita
- コメント・概略図の参考にさせていただいた
- 修正方針の参考：next_permutation の勉強とRubyでの実装 - Qiita
同様の考え方で、前の順列を求める prev_permutation も作れる。単に不等号の向きを逆転させればいい（等号の有無は変えないこと）。
- の部分を参考にさせてもらってprev_permutationを実装した
