조합, 순열 알고리즘

완전탐색, 부르트포스, 구현등의 유형에서 많이 나오는 알고리즘. 중요하니까 정리해보자. 

조합

중복을 허용하지 않음.

123이나 231이나 321은 다 똑같음.

조합은 dfs로 구현하거나 이진법 또는 점화식을 이용하여 구현할 수 있음. dfs로 n개의 숫자에 대해 r개로 이루어진 조합을 구하는 코드는 

let n = [1,2,3,4,5]
let r = 3
var comb: [Int] = Array(repeating:0 ,count:r)

func dfs(depth: Int, beginWith: Int) {
    if depth == r {
        print(comb)
        return
    }
    for i in beginWith..<n.count {
        comb[depth] = n[i]
        dfs(depth: depth+1, beginWith: i+1)
    }
}

for i in 0..<r {
    dfs(depth: 0, beginWith: n[i])
}

이 조합 코드를 이용하면 부분 수열도 구할 수 있음. 부분수열은 n개의 숫자가 1개일때의 조합, 2개일때, 3개일때...n개일때이므로 for문을 이용해 이를 구현.

let n = [1,2,3,4,5]
var currentCombNum = 0
var comb: [Int] = []

func dfs(depth: Int, beginWith: Int) {
    if depth == currentCombNum {
        print(comb)
        return
    }
    for i in beginWith..<n.count {
        comb[depth] = n[i]
        dfs(depth: depth+1, beginWith: i+1)
    }
}

for i in 1..<n.count {
    comb = Array(repeating: 0, count: i)
    currentCombNum = i
    for j in 0..<n.count {
        dfs(depth: 0, beginWith: n[j])
    }
}

순열 

중복 허용. 순서가 다르면 다른 경우임.

123, 231, 321은 모두 다른 경우. dfs를 이용해서 구현.

import Foundation

let n = [1,2,3,4,5]
var r = 3
var comb: [Int] = Array(repeating: 0, count: r)
var visited: [Bool] = Array(repeating: false, count: n.count)

func dfs(selectNum: Int, depth: Int) {
    if depth == r {
        print(comb)
        return
    }
    for i in 0..<n.count {
        if !visited[i] {
            visited[i] = true
            comb[depth] = n[i]
            dfs(selectNum: i, depth: depth+1)
            visited[i] = false
        }
    }
}

for i in 0..<n.count {
    visited[i] = true
    dfs(selectNum: i, depth: 0)
    visited[i] = false
}