[Kotlin] Algorithms - Permutation

Permutation

Choose r from different n elements without duplication and list them in order.

It is an extended concept from the combination, and unlike the combination, there is an order.

Processing using visit or not array

1. Visit all indexes with Depth-First Search (DFS).
2. Check the visit to avoid duplicating the value.
3. Repeat the above process until the depth matches r.

Code 1. n!

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
    }
}

Code 2. nPr + generic type for all data types

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
}

Code 3. nPr + Processing using swap

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
}

Result

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

Reference

https://velog.io/@chayezo/Algorithm-순열-조합

https://hanyeop.tistory.com/455

https://notepad96.tistory.com/111

https://programming4myself.tistory.com/94

https://velog.io/@soyeon207/알고리즘-순열-yaxs0hh7

https://gyeong-log.tistory.com/51

https://soopeach.tistory.com/157

https://velog.io/@heyday_7/알고리즘-순열과-조합

[Kotlin] Algorithm - Combination - Dico

알고리즘 조합을 kotlin으로 구현

dico.me

[Kotlin] Algorithm - Recursive - Dico

알고리즘 재귀(Recursive)를 코틀린으로 설명

dico.me