[Swift] 순열과 조합 구현

지난 포스팅에서 Queue를 구현해봤는데요

알고리즘 문제에는 순열 및 조합도 가끔 쓰이죠!

 

그래서 이번엔 순열과 조합을 구현해봤습니다.

---

순열 (Permutation)

순열은 전체에서 중복없이 순서를 고려해 n개를 배열하는 경우의 수입니다.

해당 특성에 맞게 DFS를 사용해 접근했습니다.

 

따라서 Stack과 재귀함수 둘 모두를 사용할 수 있습니다.

Stack 사용

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
}

조합 (Combination)

조합은 전체에서 중복없이 순서를 고려하지않고 n개를 배열하는 경우의 수입니다.

해당 특성에 맞게 DFS를 사용해 접근했습니다.

 

따라서 이 역시 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 {
        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
}