はじめに

普段、KotlinでAtCoderをやっています。AtCoderではたまに順列の全探索をしたいことがあります。C++やPythonだと標準ライブラリにそのための機能があるのですが、Kotlinにはありません。なので作ってみました。
先駆者がいらっしゃるのは知っていましたが、練習がてら自分でやってみたかったのでやってみました。
既存のコードを見ながらだとほぼ写経になってしまいそうだったので、どんな感じで実装するのかだけ調べて、既存コードは参照せずに書きました。

順列の全探索とは？

順列の全探索というのは、要するにある配列の並べ替えのパターンを全部調べるということです。

たとえばこのような配列があったとしたら

[1, 2, 3]

並び替えのパターンとしては以下の6通りが存在します。

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

つまり、元の配列を与えたらその並び替えパターンを上記のように全部出してくれる機能が欲しいということです。

アルゴリズム

どんな感じで実装できるのかなーと雰囲気を掴むためにググって、以下のサイトを見ました。

直接自分で実装する例は載っていないですが、以下のことがわかります。

並べ替えのパターンは、配列の長さを$N$とすると$N!$通りある
再帰を使って実装できる

たしかに組み合わせは樹形図で表現できるので階乗通りになりますし、それをDFS（深さ優先探索）すればいかにもできそうです。

実装

以下のようになりました。

やっていることをざっくり書くと、添字を全列挙してそれをベースの配列（MutableList）に書き込んでしまいます。元の値が失われないように queue にコピーしていて、それを順次読み書きしていきます。
添字を列挙していることで任意の型に対して使えるようになっているのでジェネリクスを使いました。

一般的に多重ループは再帰に置き換えられるので、そのようにしています。配列の長さが固定ではないので多重ループだと実装が面倒そうです。

class Permutation<T>(private val list: MutableList<T>) {
    private val queue = ArrayDeque(list)

    fun forEach(action: (MutableList<T>) -> Unit) {
        forEach(0 ,0, action)
    }

    private fun forEach(count: Int, layer: Int, action: (MutableList<T>) -> Unit) {
        if(count == list.size) {
            action(list)
            return
        }

        for(i in count until list.size) {
            val elem = queue.removeFirst()
            list[layer] = elem
            forEach(count + 1, layer + 1, action)
            queue.add(elem)
        }
    }
}

使い方としては以下のような感じ。

val list = (1..5).toMutableList()
val permutation = Permutation(list)
permutation.forEach {
    println(it)
}

列挙した値を使って行う処理をラムダ式を渡す方式としています。C++の next_permutation とはだいぶ使い方が異なりますが、このほうが使いやすい気がしました。実装も楽ですし。

これを使って、以下の問題を解きました。

一応ネタバレ配慮

D - Unique Username
https://atcoder.jp/contests/abc268/tasks/abc268_d

解答はこちら。
https://atcoder.jp/contests/abc268/submissions/46786634

いまいちな点

実行結果と計算量はたぶん問題ないと思いますが、突貫工事なので全然洗練されていないです。

コンストラクタで渡した値を書き換えてしまう
- コピーのコストをケチった
count と layer を分ける意味…？
forEach しかない
inline化されていないので直returnできない

あたり？

Kotlinで順列全探索（Permutation）

はじめに

順列の全探索とは？

アルゴリズム

実装

いまいちな点