kotlinで順列

2020年10月2日2022年10月27日kotlin

n個の数字（0 .. n-1）から、k個を取る順列。

next()関数を呼ぶと次の候補が取得される。
先に作っておくのではなく、前の候補から次の候補を計算する。
内部配列は逆順に保持していて、next()関数では逆順に変換してから返す。

nを20までにしているのは、sizeの計算で落ちてしまうから。
Hit And Blow用に使っているので、n=10しか使わないから十分。

使用方法。

/**
 * 0..n-1から、k個の順列
 */
class Perm(val n: Int, val k: Int) {
    private lateinit var current: IntArray

    val size: Long get() = LongArray(k) { (n - it).toLong() }.reduce { acc, i -> acc * i }

    init {
        require(n in 1..20 && k > 0 && n > k) { "wrong parameters."}
        clear()
    }

    fun clear() {
        current = IntArray(k) { k - it - 1 }
    }


    fun next(): IntArray {
        var result = current
        current = IntArray(k) { result[it] }
        do {
            increment(current, 0)
        } while (isDuplicated(current))
        return result.reversedArray()
    }

    //重複があれば true を返す。
    private fun isDuplicated(v: IntArray): Boolean {
        for(i in 0 until k - 1) {
            for(j in i + 1 until k) {
                if(v[i] == v[j]) return true
            }
        }
        return false
    }

    //n 進数k 桁の数値をインクリメント（重複含む）
    private fun increment(v: IntArray, cnt: Int) {
        if (cnt >= k) {
            v.fill(0)
        } else {
            v[cnt]++
            if (v[cnt] >= n) {
                //桁上がり
                v.fill(0, 0, cnt + 1)
                increment(v, cnt + 1)
            }
        }
    }
}

//10個の数値から４個を取る順列
val p = Perm(10, 4)
println("size=" + p.size)
for (i in 0 until p.size) {
    val ans = p.next()
    println("${i} : ${ans.joinToString(separator = ",")}")
}