Solving https://codeforces.com/problemset/problem/1716/B

PermutationChain.kt

//fun debugln(str: String) = println(str)
fun debugln(@Suppress("UNUSED_PARAMETER") unused: String) = {}

fun search(chainLen: Int) : List<List<Int>> {
    assert(chainLen > 0)
    val start = (0 until chainLen).map { it }.toList()

    fun swap(list: List<Int>, a: IndexedValue<Int>, b: IndexedValue<Int>) : MutableList<Int> {
        val result = list.toMutableList()
        result[a.index] = b.value
        result[b.index] = a.value
        return result
    }

    fun permutate(prev: List<Int>) : List<Int> {
        // Find a fixed point. If there is none, we cannot continue the permutation.
        val a = prev.withIndex().find { it.index == it.value }
        if (a == null) {
            debugln("We're done!")
            return listOf<Int>()
        }

        // Find a non-fixed point that won't become one after the swap.
        // This candidate will reduce the fixeness by 1, so should come first.
        val b = prev.withIndex().find {  it.index != it.value && it.index != a.index && it.value != a.index }
        if (b != null) {
            debugln("Good one!")
            return swap(prev, a, b)
        }

        // Find another fixed point.
        val c = prev.withIndex().find {  it.index == it.value && it.index != a.index }
        if (c != null) {
            debugln("So so one!")
            return swap(prev, a, c)
        }

        debugln("Not found")
        return listOf<Int>()
    }

    val seq : Sequence<List<Int>> = generateSequence(start, ::permutate)
    return seq.takeWhile { !it.isEmpty() }.toList()
}

fun main() {
    val nprobs = readLine()!!.toInt()
    repeat(nprobs) {
        val chainLen = readLine()!!.toInt()
        debugln("$chainLen")
        val result = search(chainLen)
        println("${result.size}")
        result.forEach {
            println(it.map { (it + 1).toString() }.joinToString(separator=" "))
        }
    }
}