[Swift] 조합(combination), 순열(permutation)

✅ 조합 vs 순열 차이

- 순열 : AB, BA가 다름 (순서가 중요하기 때문에)

- 조합 : AB, BA가 똑같음 (순서가 중요하지 않음)

예를들어 자물쇠 번호를 123으로 해야만 풀리고 321로는 풀리지 않듯이, 순서가 중요한 것이 순열이며

샐러드에 닭가슴살을 넣은 다음 드레싱을 넣든, 드레싱을 넣은 다음 닭가슴살을 넣든 결과는 똑같기 때문에 순서는 중요하지 않는 것이 조합이다.

 

조합

- 순서와 상관없이, 중복 없이 n개중에 r개를 선택한 경우들을 나열

- 예를들어 [1, 2, 3]에서 서로 다른 2개의 원소를 뽑아 나열하는 경우, 중복을 고려해야하기 때문에 (1, 2), (1, 3), (2, 3)의 경우의 수가 존재한다.

- 조합 공식 :

func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()

    func combination(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }

    combination(0, [])

    return result
}

 

순열

- 순서와 상관 있고, 중복을 고려하지 않고 n개 중에 r개를 선택한 경우들을 나열

- 예를들어 [1, 2, 3]에서 서로 다른 2개의 원소를 뽑아 나열하는 경우, 중복을 고려하지 않기 때문에 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 의 경우의 수가 존재한다.

- 순열 공식 :

시간복잡도 O(n^n) 코드

// 구현해놓은 Permutation 연습
func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()
    var visited = [Bool](repeating: false, count: nums.count)
    
    func permutation(_ nowPermute: [Int]) {
        if nowPermute.count == targetNum {
            result.append(nowPermute)
            return
        }
        for i in 0..<nums.count {
            if visited[i] == false {
                visited[i] = true
                permutation(nowPermute + [nums[i]])
                visited[i] = false
            }
        }
    }
    permutation([])
    
    return result
}

 

시간복잡도 O(n!) 코드

var arr:[Int] = [1, 2, 3]

func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
  var result = [[Int]]()
  
  func permutation(_ depth: Int) {
    if depth == targetNum {
      result.append(Array(arr[0..<depth]))
      return
    }
    
    for i in depth..<nums.count {
      arr.swapAt(i, depth)
      permutation(depth+1)
      arr.swapAt(i, depth)
    }
  }
  permutation(0)
  
  return result
}

print(permute(Array(1...3), 3))