순열, 조합 by Kotlin

순열, 조합

순열(Permutation)

---

순서가 중요한 경우

nPr = n! / (n-r)! (n : 전체 개수, r : 뽑을 개수)

조합(Combination)

---

순서가 중요하지 않은 경우

nCr = n! / r! * (n-r)!

비교

---

5명 중에서 3명을 뽑는 경우

• 순열
  • 3명을 1,2,3 등 순서대로 뽑는 경우
  • ₅P₃ = 5! / (5-3)! = 60
• 조합
  • 3명을 순서 상관없이 뽑는 경우
  • ₅C₃ = 5! / 3! * (5-3)! = 10

순열 구현

---

// Collection<T>에 순열 함수 P를 추가
internal inline infix fun <reified T : Any> Collection<T>.P(r: Int): List<List<T>> =
    toMutableList().permutations(0, r) // 원소 리스트를 순열 함수에 넘김

// 실제 순열을 구하는 함수
private fun <T : Any> MutableList<T>.permutations(depth: Int, r: Int): List<List<T>> = if (depth == r) {
    listOf(subList(0, r).toList()) // 원하는 길이 r만큼의 부분 리스트 생성
} else {
    val permutations = mutableListOf<List<T>>() // 결과를 저장할 리스트
    for (i in depth until size) {
        swap(i, depth) // i와 depth 위치의 원소를 바꿈
        permutations.addAll(permutations(depth + 1, r)) // 재귀 호출로 순열 계산
        swap(i, depth) // 원래의 상태로 복귀
    }
    permutations // 순열 결과 반환
}

// 리스트 내의 두 원소의 위치를 바꾸는 함수
private fun <T : Any> MutableList<T>.swap(i: Int, j: Int) {
    val temp = this[i] // 임시 변수에 i 위치의 원소를 저장
    this[i] = this[j] // j 위치의 원소를 i 위치로 이동
    this[j] = temp // 임시 변수에 저장한 원소를 j 위치로 이동
}

조합 구현

---

// Collection<T>에 조합 함수 C를 추가
internal inline infix fun <reified T : Any> Collection<T>.C(r: Int): List<List<T>> =
    toMutableList().combinations(BooleanArray(size), 0, r) // 원소 리스트를 조합 함수에 넘김

// 실제 조합을 구하는 함수
private fun <T : Any> MutableList<T>.combinations(visited: BooleanArray, start: Int, r: Int): List<List<T>> =
    if (r == 0) {
        listOf(filterIndexed { index, _ -> visited[index] }) // 선택된 원소만을 가진 리스트 생성
    } else {
        val combinations = mutableListOf<List<T>>() // 결과를 저장할 리스트
        for (i in start until size) {
            visited[i] = true // 원소를 선택함을 표시
            combinations.addAll(combinations(visited, i + 1, r - 1)) // 재귀 호출로 조합 계산
            visited[i] = false // 원소 선택 해제
        }
        combinations // 조합 결과 반환
    }

결과

---

fun main() {
    val list = listOf("A", "B", "C") // 원소 리스트 생성
    
    val permutations = list P 2 // 순열 계산
    val combinations = list C 2 // 조합 계산

    println(permutations) // 순열 출력
    // [[A, B], [A, C], [B, A], [B, C], [C, B], [C, A]]

    println(combinations) // 조합 출력
    // [[A, B], [A, C], [B, C]]
}