[Algorithm] Permutation & Combination(순열과 조합)

순열과 조합 코드를 작성해보자.

Python에서 직접 코드를 작성할 필요가 없다.

from itertools import permutations
from itertools import combinations

data = [1, 2, 3]
list(permutations(data, 2))  # (1, 2), (1, 3), (2, 1), ...
list(combinations(data, 2))  # (1, 2), (1, 3), (2, 3)

이렇게 제공되는 함수가 있기 때문에 원하는 개수에 맞는 순열, 조합 요소를 뽑아준다.

 

하지만 Swift에서는 직접 구현해야하니...

한번 작성해보자.

순열

원하는 함수 형태는 다음과 같다.

func permutations<T>(data: [T], count: Int) -> [[T]]?

제네릭을 사용하여 만들어보자.

data의 길이와 count가 정상적이지 않으면 nil 값을 반환시키기 위해 옵셔널 반환값을 사용했다.

guard data.count >= count else { return nil }

또한 Python의 permutations 코드를 참고했는데, DFS를 활용한 구조였다.

[Algorithm] Depth-First Search(DFS)

// 최종 결과
var result: [[T]] = [] 

// 순열 요소를 생성하여 result에 추가될 buffer
var buffer: [T] = []

// Index 방문 여부 확인
var visited = Array(repeating: false, count: data.count)

permutations 내부에 중첩 함수를 정의한다.

func nextElement() {
    if buffer.count == count {
        result.append(buffer)
        return
    }
    for i in 0..<data.count {
        if !visited[i] {
            visited[i] = true
            buffer.append(data[i])
            nextElement()
            buffer.removeLast()
            visited[i] = false
        }
    }
}

DFS 구조로 돌면서 요소를 추가하고, buffer의 길이가 count가 되면 result에 추가된다.

최종코드

func permutations<T>(data: [T], count: Int) -> [[T]]? {
    guard data.count >= count else { return nil }
    var result: [[T]] = []
    var buffer: [T] = []
    var visited = Array(repeating: false, count: data.count)

    func nextElement() {
        if buffer.count == count {
            result.append(buffer)
            return
        }
        for i in 0..<data.count {
            if !visited[i] {
                visited[i] = true
                buffer.append(data[i])
                nextElement()
                buffer.removeLast()
                visited[i] = false
            }
        }
    }
    nextElement()
    return result
}

조합

마찬가지로 아래의 형태로 정의한다.

func combinations<T>(data: [T], count: Int) -> [[T]]?

여기서도 개수에 대한 예외처리를 해준다.

guard data.count >= count else { return nil }

DFS 구조를 동일하지만, 순서에 영향을 받지 않기 때문에 방문여부를 따로 체크할 필요가 없다.

var result: [[T]] = []
var buffer: [T] = []

똑같이 중첩 함수를 작성한다.

func nextElement(index: Int) {
    print(buffer)
    if buffer.count == count {
        result.append(buffer)
        return
    }
    if index >= data.count { return }
    buffer.append(data[index])
    nextElement(index: index + 1)
    buffer.removeLast()
    nextElement(index: index + 1)
}

최종코드

func combinations<T>(data: [T], count: Int) -> [[T]]? {
    guard data.count >= count else { return nil }
    var result: [[T]] = []
    var buffer: [T] = []
    
    func nextElement(index: Int) {
        print(buffer)
        if buffer.count == count {
            result.append(buffer)
            return
        }
        if index >= data.count { return }
        buffer.append(data[index])
        nextElement(index: index + 1)
        buffer.removeLast()
        nextElement(index: index + 1)
    }
    nextElement(index: 0)
    return result
}

Conclusion

순열과 조합 각각의 시간 복잡도는 개수에 따라 다르다.

우리가 익히 알고 있는 공식

                    n!
Permutation nPr = ------ * r
                  (n-r)!
                  
                       n!
Combination nCr = ----------- * r
                  r! * (n-r)!

이 곧 시간복잡도가 된다.

 

또한 Python Itertools의 permutation과 combination 함수를 참조하면서 yield라는 신기한 키워드를 발견했다.

찾아보니 Python의 Generator Expressions, Yield Expressions와 관련이 있다고 한다.

Swift에서도 비슷한 기능을 구현할 수 있다고 하니 다음에 알아보자.

Reference

https://docs.python.org/ko/3/library/itertools.html

itertools — Functions creating iterators for efficient looping