[Kotlin] 알고리즘 - 순열(Permutation)

순열(Permutation)

서로 다른 n개를 가진 원소에서 r개를 중복없이 골라 순서대로 나열한다.

조합에서 확장된 개념으로, 조합과 달리 순서가 있다.

방문 여부 배열을 이용한 처리 과정

1. 깊이 우선 탐색(DFS, Depth-First Search)으로 모든 원소를 방문한다.
2. 방문 여부를 확인하여 값이 중복되지 않게 한다.
3. 깊이가 r과 일치할 때까지 위 과정을 반복한다.

코드 1. n!

private const val alphabets = "ABC"
private lateinit var result: Array<Char> // 정렬된 알파벳
private lateinit var visited: Array<Boolean> // 순열 방문 여부

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

    permutation()
}

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

코드 2. nPr + 제네릭 타입으로 모든 데이터 타입 대응

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

/**
 * 순열
 *
 * @param elements: n개 원소를 가진 배열
 * @param r: 추출할 원소 수
 */
fun <T> permutation(elements: Array<T>, r: Int): List<List<T>> {
    val visited = BooleanArray(elements.size) // 방문 여부
    val results = mutableListOf<List<T>>() // 모든 경우의 수

    val result = elements.sliceArray(0 until r) // 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
}

코드 3. nPr + 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
}

결과

[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/알고리즘-순열과-조합