[Kotlin] 순열 구하기

 

 

코틀린에서 순열을 구하는 방법. 

 

1. 순열의 개념

순열이란 순서에 상관있는 배열을 말합니다. 예를 들어, 숫자 배열 [1, 2, 3]에서 순열을 구하면 다음과 같은 모든 조합이 나옵니다:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]
  
  

이런 조합들을 구하는 것이 순열. 

 

fun getPermutations(arr: MutableList<Int>, depth: Int, n: Int, result: MutableList<List<Int>>) {
    if (depth == n) {
        result.add(arr.toList())  // 배열의 복사본을 추가
        return
    }

    for (i in depth until n) {
        arr.swap(depth, i)  // 요소 교환
        getPermutations(arr, depth + 1, n, result)
        arr.swap(depth, i)  // 다시 원래 상태로 복원
    }
}

// 배열의 두 요소를 교환하는 확장 함수
fun MutableList<Int>.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

 

 

2. 재귀로 순열 구하기

순열을 구하는 알고리즘은 각 자리의 숫자를 고정하고, 나머지 숫자들의 순열을 재귀적으로 구하는 방식입니다.

 

3. 주요 과정

• 재귀 호출: getPermutations 함수는 현재 자리(depth)의 숫자를 고정하고, 나머지 자리에 대해 순열을 재귀적으로 구합니다.
• swap: 각 자리의 숫자를 교환하여 다른 순서를 만듭니다.
• 종료 조건: depth가 배열의 길이와 같아지면 그때까지 만든 순열을 결과에 추가합니다.

이 방식으로 숫자의 모든 순열을 구할 수 있습니다.