[Swift] 순열

1. 순열이란?

순열은 주어진 원소들로 만들 수 있는 모든 순서의 조합을 의미합니다. 가장 쉽게 설명하자면, n개의 원소 중에서 r개를 선택하여 순서를 고려해 나열하는 것입니다.

예시를 통한 이해

예를 들어, [1, 2, 3] 이라는 세 개의 숫자가 있다고 해볼까요?

이 중에서 2개를 선택하여 나열하는 경우의 수는 다음과 같습니다.

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

 

2. 순열의 종류

2.1 일반 순열 (Permutation)

• 각 원소를 한 번씩만 사용
• nPr = n!/(n-r)! 의 공식 사용
• 예: [A, B, C] 중 2개 선택 → [A,B], [A,C], [B,A], [B,C], [C,A], [C,B]

2.2 중복 순열 (Permutation with Repetition)

• 각 원소를 여러 번 사용 가능
• n^r 의 공식 사용
• 예: [A, B] 중 2개 선택 → [A,A], [A,B], [B,A], [B,B]

 

3. 순열의 실제 구현

3.1 일반 순열

func permutation(_ targetArr: [String], _ arr: [String]) {
    if arr.count == 2 {  // 2개를 선택하는 경우
        result.append(arr)
        return
    }
    
    for i in 0..<targetArr.count {
        if !arr.contains(targetArr[i]) {
            permutation(targetArr, arr + [targetArr[i]])
        }
    }
}

 

일반적인 순열은 중복을 포함하지 않기때문애 현재 인자를 포함하고 있는지 포함하고 있지 않은지를 조건문으로 만들어두고 재귀 방식으로 접근한다.

 

3.2 중복 순열

func permutationWithDuplicates(_ targetArr: [String], _ arr: [String]) {
    if arr.count == 2 {  // 2개를 선택하는 경우
        result.append(arr)
        return
    }
    
    for i in 0..<targetArr.count {
        permutationWithDuplicates(targetArr, arr + [targetArr[i]])
    }
}

 

조건이 없는 것을 볼 수 있다.