[Kotlin] Algorithms - Permutation

kotlin

private const val alphabets = "ABC"
private lateinit var result: Array<Char> // Altered Alphabet
private lateinit var visited: Array<Boolean> // Permutation visit status

fun main() {
    result = Array(alphabets.length) { '_' }
    visited = Array(alphabets.length) { false }

    permutation()
}

fun permutation(depth: Int = 0) {
    if (depth == alphabets.length) {
        println(result.contentDeepToString()) // a complete permutation
        return
    }
    
    for (i in alphabets.indices) {
        if (visited[i]) continue
        
        result[depth] = alphabets[i]
        visited[i] = true
        permutation(depth + 1)
        visited[i] = false
    }
}

kotlin

fun main() {
    permutation(arrayOf("A", "B", "C"), 3).forEach {
        println(it)
    }
}

/**
 * Permutation
 *
 * @param elements: an array of n elements
 * @param r: Number of elements to extract
 */
fun <T> permutation(elements: Array<T>, r: Int): List<List<T>> {
    val visited = BooleanArray(elements.size) // Visit or not
    val results = mutableListOf<List<T>>() // the number of all cases

    val result = elements.sliceArray(0 until r) // As a result of sorting r

    fun recursionPermutation(depth: Int = 0) {
        if (depth == r) {
            results.add(result.toList())
            return
        }

        for (i in elements.indices) {
            if (visited[i]) continue
            
            visited[i] = true
            result[depth] = elements[i]
            recursionPermutation(depth + 1)
            visited[i] = false
        }
    }

    recursionPermutation()
    return results
}

kotlin

fun main() {
    permutation(arrayOf("A", "B", "C"), 3).forEach {
        println(it)
    }
}

fun <T> permutation(elements: Array<T>, r: Int): List<List<T>> {
    val n = elements.size
    val results = mutableListOf<List<T>>() // 모든 경우의 수

    fun swapPermutation(depth: Int = 0) {
        if (depth == r) {
            results.add(elements.takeLast(r).toList())
            return
        }

        for (i in range(depth, n)) {
            var tmp = elements[i]
            elements[i] = elements[depth]
            elements[depth] = tmp

            swapPermutation(depth + 1)

            // 원위치
            tmp = elements[i]
            elements[i] = elements[depth]
            elements[depth] = tmp
        }
    }

    swapPermutation()
    return results
}

text

[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]