순열과 조합 Swift

순열 Permutation

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

 

ex) [1, 2, 3]의 배열에서 두개의 원소를 뽑는다고 한다면

[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]이 된다.

여기서 [1,2] 와 [2,1]은 들어있는 원소는 같지만, 순서가 다르기때문에 다른 경우의수로 판단한다.

 

import Foundation

// 순열
func permutation(_ targetArr: [Int],_ targetNum: Int,_ arr: [Int]) {
    // 뽑으려는 갯수와 동일한경우
    if arr.count == targetNum {
        print(arr)
        return
    }
    // 순열은 순서가 상관있는 뽑기방식으로, [2,1] != [1,2]이다.
    // 그러므로 반복문을 처음부터 시작한다.
    for i in 0..<targetArr.count {
        // 중복되는값이 아니라면 추가한다.
        if !arr.contains(targetArr[i]) {
            permutation(targetArr, targetNum, arr + [targetArr[i]])
        }
    }
}

permutation([1,2,3,4], 2, [])

// 출력
//[1, 2]
//[1, 3]
//[1, 4]
//[2, 1]
//[2, 3]
//[2, 4]
//[3, 1]
//[3, 2]
//[3, 4]
//[4, 1]
//[4, 2]
//[4, 3]

 

조합 Combination

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

 

ex) [1, 2, 3]의 배열에서 두개의 원소를 뽑는다고 한다면

[1,2], [1,3], [2,3]이 된다.

순열과 다르게 순서와 상관이 없으므로 [1,2], [2,1]은 같은 경우의수로 판단한다

 

import Foundation

// 조합
func combi(_ targetArr: [Int],_ targetNum: Int,_ index: Int,_ arr: [Int]) {
    // 뽑으려는 수만큼 뽑았다면 출력
    if arr.count == targetNum {
        print(arr)
        return
    }
    // 순열과 다르게 순서가 달라도 들어있는 원소가 같다면 같은 경우의 수로 판단한다.
    // 그래서 뽑은 원소 바로 다음 원소를 추가하고 재귀호출
    for i in index..<targetArr.count {
        combi(targetArr, targetNum, i+1, arr + [targetArr[i]])
    }
}

combi([1,2,3,4], 2, 0, [])

// 출력
//[1, 2]
//[1, 3]
//[1, 4]
//[2, 3]
//[2, 4]
//[3, 4]

 

 

※ 틀린 부분이나 오류나는 부분 알려주시면 감사하겠습니다 (_ _)