要約
C++ や Python で順列の前列挙をしたい場合は next_permutation を使うと便利ですが、Kotlin にはそれがありません。
本記事では、Kotlin で順列を生成するコードスニペットの紹介と、動作解説をします。
Kotlinの基本的な文法は分かるけど、再帰を自分で１から書くのは難しいと感じるAtCoder緑前後までの競プロer (私です) を対象としています。
例題
ABC183 C - Travel
入力：N(2~8)頂点と、各頂点間の距離、正整数K
出力：頂点1で始まり頂点1で終わる各頂点をちょうど1度ずつ訪問するパスのうち、長さがKとなるパスの数
回答方針
- パスの頂点1以外の頂点の並び順を全通り生成（制約が
N<=8なので8!=40320通りを全列挙しても問題ない） - それぞれのパスの長さがKかチェックする
2については、順列の列挙ができればあとは足し算を行うのみなので、本記事では割愛します。
順列生成
C++ や Python で順列の前列挙をしたい場合は next_permutation を使うと便利ですが、Kotlin にはそれがありません。
例えば[1, 2, 3]という要素を持つリストから、[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]という順列のセットを生成するにはどうすれば良いでしょうか。
Kotlin では、下記のコードにより、任意のリストから順列を生成できます。
Permutation.Kt
fun <T> generatePermutations(source: List<T>): Set<List<T>> {
val permutations = mutableSetOf<List<T>>()
fun permutation(source: List<T>, perm: List<T>) {
if (source.size <= 1) {
permutations += perm + source
} else {
repeat(source.size) {
permutation(source.take(it) + source.drop(it + 1), perm + source[it])
}
}
}
permutation(source, emptyList())
return permutations
}
以下、簡単に動作の解説をします。
- permutation() は再起関数になっています。
- permutation() の引数 source は残りの順列化する要素のリスト、perm は現在までに確定している順列を保持しておく変数です。
- 1回の permutation() が果たす役割は、「sourceから1要素を選んでpermの末尾に追加 (とsourceから削除) し次の再帰に突入」をsourceの全要素に対して行うこと、となります。
- sourceの要素が1要素になると、それを末尾につなげて一つの順列が完成するので、返却用のmutableSetに登録します。
- 初期状態は、generatePermutationsに渡されたsourceで、構築途中の順列はないので空のリストを渡して、順列を作成します。
自分の提出
提出 #18704381 - AtCoder Beginner Contest 183
本記事は以上になります。
間違いや改善点などありましたらご指摘よろしくお願いします。