[Swift] 순열 구현하기 feat.재귀

파이썬은 permutations라는 내장함수가 있지만 swift는 만들어서 써야함

 

func permuteWirth(_ a: [T], _ n: Int) {
    if n == 0 {
        print(a)     // 순열 완성시 출력
    } else {
        var a = a        
        permuteWirth(a, n - 1)        // 1. 현재 상태로 재귀
        for i in 0..<n {
            a.swapAt(i, n)            // 2. 스왑
            permuteWirth(a, n - 1)    // 3. 재귀 호출
            a.swapAt(i, n)            // 4. 백트래킹 (원상복구)
        }
    }
}

permuteWirth(array, array.count - 1)

출처

 

음~ 뭔말이지

 

✅ 알고리즘 동작 원리

1. 종료 조건: n == 0이면 순열 완성
2. 첫 번째 재귀: 현재 상태 그대로 더 깊이 탐색
3. 스왑 + 재귀: i번째와 n번째를 바꿔가며 모든 경우 탐색
4. 백트래킹: 스왑을 되돌려 다른 경우 탐색 준비

✅ 실행 과정 예시 

permuteWirth([A,B], 1)
├─ 현재 상태로 재귀: permuteWirth([A,B], 0) → 출력: [A,B]
├─ 0↔1 스왑: [B,A] → permuteWirth([B,A], 0) → 출력: [B,A]
└─ 되돌리기: [A,B]

permuteWirth([A,B,C], 2)
├─ 현재 상태로 재귀: permuteWirth([A,B,C], 1)
├─ 0번과 2번 스왑: [C,B,A] → permuteWirth([C,B,A], 1)  
├─ 1번과 2번 스왑: [A,C,B] → permuteWirth([A,C,B], 1)
└─ 2번과 2번 스왑: [A,B,C] → permuteWirth([A,B,C], 1)

  

 

✅ 재귀 이해하기

func visualizeCallStack(_ n: Int, level: Int = 0) {
    let indent = String(repeating: "│  ", count: level) + "├─ "
    print("\(indent)함수(\(n)) 실행 중...")
    
    if n == 0 {
        print("\(indent)종료 조건 도달!")
        return
    }
    
    print("\(indent)자기 자신 호출: 함수(\(n-1))")
    visualizeCallStack(n - 1, level: level + 1)
    print("\(indent)함수(\(n)) 완료")
}

visualizeCallStack(3)

 

 

✅ 모든 순열 배열 반환하도록 수정

func generateAllPermutations<T>(_ array: [T]) -> [[T]] {
    guard !array.isEmpty else { return [[]] }
    
    var results: [[T]] = []
    
    func permute(_ arr: [T], _ n: Int) {
        if n == 0 {
            results.append(arr)
            return
        }
        
        var arr = arr
        permute(arr, n - 1)
        
        for i in 0..<n {
            arr.swapAt(i, n)
            permute(arr, n - 1)
            arr.swapAt(i, n)
        }
    }
    
    permute(array, array.count - 1)
    return results
}