[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
}