💡

Kotlinでクイズ：順列

2022/01/27に公開

Twitterで下記のような問題を見かけたのでKotlinで解いてみました。

[問題]
GAKKOUの6文字を並べ替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ。

まず「6文字を並べ替えてできる360個の文字列」といえば「順列」を思い浮かべますね。

文字のリストの順列を作って並べ替えたら終わりかな〜と思ったらKotlinには標準で順列を作成するライブラリ等が見つからなかったので試してみました。
※なお、今回はn個のものすべてを使った順列を扱っています。

答えを先に知りたい人はこちら

Step1: String to List<Char>

まず準備。GAKKOUという文字列をCharのリストに分解しましょう。

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()

    println(chars)
    // [G, A, K, K, O, U]

Step2: 順列を作る

リストの拡張関数として順列：Permutationsを作る関数を生やします。

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()

    println(chars.permutations())
    // [[U, O, K, K, A, G], [O, U, K, K, A, G], ... , [A, G, K, K, O, U], [G, A, K, K, O, U]]
    
    println(chars.permutations().count())
    // 720
}

fun <T> List<T>.permutations(): List<List<T>> {
    if (this.isEmpty()) return listOf(emptyList())

    val result: MutableList<List<T>> = mutableListOf()
    for (i in this.indices) {
        (this - this[i]).permutations().forEach {
            item -> result.add(item + this[i])
        }
    }
    return result
}

わかりやすさを重視して下記のようなロジックを再起で用いています（※性能は考慮していない）。

例えば[A, B, C]があったとき、

Aを除いた要素で順列を作る
-> [B, C], [C, B]
出来た順列に除いたAをつけると先頭がAの組み合わせができる
-> [B, C, A], [C, B, A]
1と2をB, Cについても実施すると[A, B, C]の順列ができる
-> [B, C, A], [C, B, A], [A, C, B], [C, A, B], [A, B, C], [B, A, C]

6個の要素の順列なので、6!=720個の組み合わせを得ることができます。

Step3: 重複を削除

GAKKOUにはKが複数含まれているのでしているので作った順列のリストには同じ組み合わせのものが含まれています。そこでListをSetにすることで重複を削除します。

これで問題にある360個の要素を得ることができます。

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()

    println(chars.permutations().toSet())
    println(chars.permutations().toSet().count())
    // 360

Step4: List<Char> to String

CharのリストをStringに戻します。

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()
    
    println(chars.permutations().toSet().map { it.toCharArray().concatToString() })
    // [UOKKAG, OUKKAG, ... , AGKKOU, GAKKOU]

Step5: 辞書式にソート

普通にソートすると辞書式（アルファベット順）に並びます。

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()
    
    println(chars.permutations().toSet().map { it.toCharArray().concatToString() }.sorted())
    // [AGKKOU, AGKKUO, ... , UOKKAG, UOKKGA]]

Step6: 100番目を取り出す

文字列のリストの100番目を取り出せば求める文字列が取得できます🙌

fun main() {
    val string = "GAKKOU"
    val chars: List<Char> = string.toList()
    
    println(chars.permutations().toSet().map { it.toCharArray().concatToString() }.sorted()[99])
    // GOKAKU

感想

標準でpermutationsをサポートしている言語も多そうですが、自分で作ってみるのも学びになりますね！もっとスマートな回答を思いつく方がいらっしゃったらぜひ教えてください😊

おまけのSwift版（Algorithmsを使ったやつ）