[Swift] 순열과 조합

개요

오랜만에 swift로 코딩 문제를 풀려고 보니 swift는 순열과 조합을 직접 구현해야 한다는 것을 깨달았다. 파이썬은 iterator였나? 아무튼 라이브러리가 있어서 쉽게 넘어갈 수 있지만 swift는 야생이다. 직접 해야된다. 그래서 준비했다. 적재적소에 쓸 수 있게 순열과 조합을 구현하였다.

순열

순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것

간단히 말해서 우리가 1,2,3에서 3개를 뽑아 순열을 구성한다고 하면 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) 총 6개로 나타낼 수 있다.

이제 순열을 코드로 구성해보자. stack을 이용한 방법과 재귀를 이용한 방법 두가지로 구성할 수 있다.

Stack을 이용한 순열 코드

• stack 초기화 단계 : 순열의 첫번째 수를 뼈대로 구성하기 위해 [element, visited]의 형태로 추가
• stack 진행 단계 : stack 값을 하나씩 꺼내서 방문하지 않은 수는 꺼낸 값에 추가해서 다시 stack에 추가
• result 추가 : stack에서 꺼낸 값의 길이가 n일 경우 result에 추가

func permutation<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var stack: [([T], [Bool])] = array.enumerated().map {
        var visited = Array(repeating: false, count: array.count)
        visited[$0.offset] = true
        return ([$0.element], visited)
    }
    
    while stack.count > 0 {
        let now = stack.removeLast()
        
        let elements = now.0
        var visited = now.1
        
        if elements.count == n {
            result.append(elements)
            continue
        }
        
        for i in 0...array.count-1 {
            if visited[i] { continue }
            visited[i] = true
            stack.append((elements + [array[i]], visited))
            visited[i] = false
        }
    }
    
    return result
}

재귀를 이용한 순열 코드

func permutation<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var visited = Array(repeating: false, count: array.count)
    
    func cycle(_ now: [T]) {
        if now.count == n {
            result.append(now)
            return
        }
        
        for i in 0..<array.count {
            if visited[i] {
                continue
            } else {
                visited[i] = true
                cycle(now + [array[i]])
                visited[i] = false
            }
        }
    }
    
    cycle([])
    
    return result
}

조합

조합 : n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것

간단히 말해서 우리가 1,2,3에서 2개를 뽑아 조합을 구성한다고 하면 (1,2), (1,3), (2,3) 총 3개로 나타낼 수 있다.

이제 순열을 코드로 구성해보자. stack을 이용한 방법과 재귀를 이용한 방법 두가지로 구성할 수 있다.

Stack을 이용한 조합 코드

func combination<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var stack = array.enumerated().map { ([$0.element], $0.offset) }
    
    while stack.count > 0 {
        // print(stack)
        let now = stack.removeLast()
        
        let elements = now.0
        let index = now.1
        
        if elements.count == n {
            result.append(elements.sorted())
            continue
        }
        
        guard index+1 <= array.count-1 else { continue }
        
        for i in index+1...array.count-1 {
            stack.append((elements + [array[i]], i))
        }
        
    }
    
    return result
}

재귀를 이용한 조합 코드

func combination<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    func cycle(_ index: Int, _ now: [T]) {
        if now.count == n {
            result.append(now)
            return
        }
        
        for i in index..<array.count {
            cycle(i + 1, now + [array[i]])
        }
    }
    
    cycle(0, [])
    
    return result
}

결론

순열은 순서를 중요시하기 때문에 방문 여부에 관한 변수 설정이 중요하다. 하지만 조합은 어차피 -> 방향으로 방문하고 끝이기 때문에 방문 여부에 관한 변수를 설정할 필요가 없다.