[Algorithm] 순열과 조합 구하기 (Swift)

반복문으로 순열 (Permuation) 구하기

순열이란 n개의 원소에서 r 개를 뽑아 순서를 구분하여 나열한 경우 (nPr) 이다. 만약 r 이 정해져 있다면 아래처럼 r 번의 반복문으로 구할 수 있다. 3개를 뽑는 경우를 고려하여 3번 반복문을 사용하기 때문에 시간복잡도는 O(n^3) 이다.

func permutations<T>(_ array: [T]) -> [[T]] {
    var permutationArray: [[T]] = []
    for i in 0..<array.count {
        for j in 0..<array.count {
            for k in 0..<array.count {
                if i == j || j == k || k == i { // 중복 제거
                    continue
                }
                permutationArray.append([array[i], array[j], array[k]])
            }
        }
    }
    return permutationArray
}

위의 코드의 단점

위의 코드의 가장 큰 단점은 r 에 대해서 자유롭지 않다는 점이다. 4개를 뽑는다면 반복문을 하나더 넣어줘야 한다. 그렇기 때문에 재귀함수를 사용하여 r 에 대응할 수 있게 만들 수 있다.

 

재귀 함수를 활용하여 순열 (Permuation) 구하기

제너릭 타입 T 를 활용한 모든 순열을 구하는 함수이다. 전체코드는 아래와 같다.

func permutations<T>(_ array: [T], _ length: Int) -> [[T]] {
    guard length >= 0 && length <= array.count else { return [] }
    
    if length == 0 {
        return [[]]
    }
    
    if length == 1 {
        return array.map { [$0] }
    }
    
    return array.enumerated().flatMap { index, element in
        var reducedArray = array
        reducedArray.remove(at: index)
        return permutations(reducedArray, length - 1).map { [element] + $0 }
    }
}

기본 조건 검사 및 종료 조건

당연히 음수개를 뽑는 경우는 없기 때문에 빈 배열을 반환하고, 뽑으려는 길이보다 배열자체가 작다면 빈 배열을 반환한다. length 가 0일 경우 하나의 빈 배열을 배열로 반환한다. length가 1일 경우에 array를 하나의 요소로 가진 배열을 배열로 반환한다.

    guard length >= 0 && length <= array.count else { return [] }
    
    if length == 0 {
        return [[]]
    }
    
    if length == 1 {
        return array.map { [$0] }
    }

 

재귀적 순열 생성

구하려는 순열의 길이가 1보다 클 경우 자기자신을 재귀적으로 호출한다. array.enumerated()를 통해 index와 element를 가져오고, 이를 flatMap 을 통해 하나의 배열로 만들어 준다. 예를들면 [[1], [2]]라면 [1, 2]로 만들어 준다.

    return array.enumerated().flatMap { index, element in
        var reducedArray = array
        reducedArray.remove(at: index)
        return permutations(reducedArray, length - 1).map { [element] + $0 }
    }

 

예를 들면 permutations([1, 2, 3], 2) 함수 호출 시 element = 1 일때 permutations([2, 3], 1) 를 호출하게 되고, 이것은 결국 [[2], [3]] 을 반환하게 되는데 이제 [1] 을 앞에 더하게 되어서 [[1, 2], [1, 3]] 을 반환하게 되고 이것을 element 가 1, 2, 3 일때 반복하게 되어서 결국 [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]] 를 반환하게 된다.

 

반복문으로  조합 (Combination) 구하기

조합이란 n개의 원소에서 r 개를 뽑아 순서를 구분하지 않고 나열한 경우 (nCr) 이다. 위처럼 3개를 뽑는 경우에는 아래와 같이 반복문으로 구할 수 있다.

func combinations<T>(array: [T]) -> [[T]] {
    var combinationArray: [[T]] = []
    
    for i in 0..<array.count {
        for j in (i+1)..<array.count {
            for k in (j+1)..<array.count {
                combinationArray.append([array[i], array[j], array[k]])
            }
        }
    }
    return combinationArray
}

 

마찬가지로 위의 코드도 몇개를 뽑냐에 따라서 반복문을 중복해줘야 해서 r 에 대응할 수 없다.

 

재귀 함수를 활용하여 조합 (Combination) 구하기

func combinations<T>(_ array: [T], _ length: Int) -> [[T]] {
    guard length >= 0 && length <= array.count else { return [] }
    
    if length == 0 {
        return [[]]
    }
    
    if length == 1 {
        return array.map { [$0] }
    }
    
    return Array(array.enumerated()).flatMap { index, element in
        let rest = Array(array.suffix(from: index + 1))
        return combinations(rest, length - 1).map { [element] + $0 }
    }
}

 

재귀적 조합 생성

순열과 차이가 있다면 이 부분일 것이다.

    return Array(array.enumerated()).flatMap { index, element in
        let rest = Array(array.suffix(from: index + 1))
        return combinations(rest, length - 1).map { [element] + $0 }
    }

 

combinations([1, 2, 3], 2) 함수를 호출 시 element = 1 일때 combinations([2, 3], 1) 를 호출하게 되고 [[2], [3]] 을 반환하게 되는데 이제 [1] 을 앞에 더하게 되어서 [[1, 2], [1, 3]] 을 반환하게 된다. 하지만 여기서부터 달라진다. element = 2 일 때 combinations([3], 1) 을 호출하게 된다. suffix 이기 때문에 다음에 있는 배열부터 다시 호출하게 된다고 보면 된다. 이렇게 하면 결국 [[1, 2], [1, 3], [2, 3]] 을 반환하게 된다.

 

이렇게 순열과 조합을 Swift 에서 구현해 보았다. 사실 재귀함수를 내가 아무런 도움없이 스스로 만들 수 있을지 모르겠다. 더 공부하고 연습해서 자유롭게 재귀함수를 만들어서 쓸 수 있게 되면 좋을 것 같다.