[Swift] 순열 / permutation / 조합 / combination

func permutation(_ target: [String], _ targetNum: Int) {
    var result: [[String]] = []
    var check = [Bool](repeating: false, count: target.count)
    
    func permute(_ arr: [String]) {
        if arr.count == targetNum {
            result.append(arr)
            return
        }
        
        for i in 0..<target.count where !check[i] {
            check[i] = true
            permute(arr + [target[i]])
            check[i] = false
        }
    }
    
    permute([])
    print(result)
}


permutation(["a","b","c","d"], 2) 
// [["a", "b"], ["a", "c"], ["a", "d"], ["b", "a"], ["b", "c"], ["b", "d"], ["c", "a"],
// ["c", "b"], ["c", "d"], ["d", "a"], ["d", "b"], ["d", "c"]]

permutation(["a","b","c","d"], 3)
// [["a", "b", "c"], ["a", "b", "d"], ["a", "c", "b"], ["a", "c", "d"], ["a", "d", "b"],
// ["a", "d", "c"], ["b", "a", "c"], ["b", "a", "d"], ["b", "c", "a"], ["b", "c", "d"], 
// ["b", "d", "a"], ["b", "d", "c"], ["c", "a", "b"], ["c", "a", "d"], ["c", "b", "a"], 
// ["c", "b", "d"], ["c", "d", "a"], ["c", "d", "b"], ["d", "a", "b"], ["d", "a", "c"], 
// ["d", "b", "a"], ["d", "b", "c"], ["d", "c", "a"], ["d", "c", "b"]]

 

위의 코드는 메모리초과가 날 위험이 있다.

 

let arr = ["1", "2", "3", "4"]
let n = arr.count
var check = [Bool](repeating: false, count: n)
var result: [String] = []

func permutation(_ currentDepth: Int) {
	if currentDepth == n {
		print(result.joined(separator: " "))
		return
	}

	for i in 0..<n where !check[i] {
		check[i] = true
		result.append(arr[i])
		permutation(currentDepth + 1)
		result.removeLast()
		check[i] = false
	}
}

permutation(0)

 

 

func combi(_ targetArr: [String], _ targetNum: Int, _ index: Int, _ arr: [String]) {

    if arr.count == targetNum {
        print(arr)
        return
    }
    
    for i in index..<targetArr.count {
        combi(targetArr, targetNum, i+1, arr + [targetArr[i]])
    }
    
}

combi(["a","b","c","d"], 4, 1, ["a", "b"]) // a, b를 조합하는데, 4개까지 1번째 인덱스 부터.

// ["a", "b", "b", "c"]
// ["a", "b", "b", "d"]
// ["a", "b", "c", "d"]

 

단순 숫자로 된 조합.

func combination(_ n: Int, _ k: Int) -> UInt64 {
    var n = max(n, k), k = min(n, k)
    var result: UInt64 = 1
    for i in 0..<min(k, n - k) {      // 1. k와 n-k 중 작은 값을 사용하여 반복
        result = result * UInt64(n - i) / UInt64(i + 1) // 2. 각 단계에서 조합을 직접 계산
    }
    return result
}

1. k와 n-k 중 작은 값 사용: 𝑘와 𝑛−𝑘 중 더 작은 값으로 계산하는 이유는 조합 공식의 대칭성 때문입니다. 𝐶(𝑛,𝑘)와 𝐶(𝑛,𝑛−𝑘)는 같습니다. 더 작은 값으로 계산함으로써 필요한 반복 횟수를 줄이고, 계산의 효율성을 높일 수 있습니다.
2. 반복문 사용: 함수는 𝑘번 반복하여 각 단계마다 계산을 수행합니다. 이 반복문은 직접 팩토리얼을 계산하는 대신, 조합 공식의 각 부분을 단계별로 계산합니다.
3. 조합 계산: 각 단계에서 𝑛−𝑖를 𝑖+1로 나눔으로써, 팩토리얼의 각 부분을 즉석에서 계산합니다. 이는 계산 중간에 발생할 수 있는 큰 수를 피하고, 오버플로우 가능성을 줄입니다. 이 과정은 분모와 분자를 동시에 처리함으로써 결과의 정확도를 유지하면서 계산을 수행합니다.

Swifty한 Combination 

func combination(_ n: Int, _ k: Int) -> UInt64 {
	let n = max(n, k), k = min(n, k)
	if k == 0 || n == k { return 1 } // nC0은 항상 1, nCk가 같으면 1
	
	return (1...min(k, n - k)).reduce(UInt64(1)) { result, i in
		result * UInt64(n - i + 1) / UInt64(i)
	}
}