순열은 특정 집합에서 객체를 일정한 순서로 배열하는 방법이다. 예를 들어, 알파벳의 첫 다섯 글자를 사용한다면 다음은 하나의 순열이다:
a, b, c, d, e
이것은 또 다른 순열이다:
b, e, d, a, c
n개의 객체로 이루어진 집합에서 가능한 순열의 개수는 n!이다. 여기서 !는 "팩토리얼" 함수를 의미한다. 예를 들어, 다섯 글자로 이루어진 집합에서 만들 수 있는 순열의 총 개수는 다음과 같다:
5! = 5 * 4 * 3 * 2 * 1 = 120
여섯 개의 아이템으로 이루어진 집합은 6! = 720개의 순열을 가진다. 열 개의 아이템은 10! = 3,628,800개의 순열을 가진다. 이 수는 매우 빠르게 증가한다!
이 n!은 어디에서 나온 것일까? 논리는 다음과 같다: 다섯 글자로 이루어진 집합을 어떤 순서로 배열하려고 한다. 이를 위해 글자를 하나씩 선택한다. 처음에는 다섯 글자 중 하나를 선택할 수 있다: a, b, c, d, e. 이렇게 하면 5가지 가능성이 생긴다.
첫 번째 글자를 선택한 후에는 네 글자만 남게 된다. 따라서 5 * 4 = 20가지 가능성이 생긴다:
a+b b+a c+a d+a e+a
a+c b+c c+b d+b e+b
a+d b+d c+d d+c e+c
a+e b+e c+e d+e e+d
두 번째 글자를 선택한 후에는 세 글자만 남게 된다. 이런 식으로 계속 진행하면 마지막 글자는 선택의 여지가 없이 하나만 남게 된다. 따라서 가능한 총 경우의 수는 5 * 4 * 3 * 2 * 1이 된다.
Swift에서 팩토리얼을 계산하는 방법은 다음과 같다:
func factorial(_ n: Int) -> Int {
var n = n
var result = 1
while n > 1 {
result *= n
n -= 1
}
return result
}플레이그라운드에서 실행해 보자:
factorial(5) // 120을 반환factorial(20)은 이 함수로 계산할 수 있는 가장 큰 수다. 그보다 큰 수는 정수 오버플로우가 발생한다.
이제 다섯 글자로 이루어진 집합에서 3개의 요소만 선택하려고 한다. 가능한 방법은 몇 가지일까? 이전과 같은 방식으로 진행하되, 세 번째 글자에서 멈춘다. 따라서 가능한 경우의 수는 5 * 4 * 3 = 60이 된다.
이를 위한 공식은 다음과 같다:
n!
P(n, k) = --------
(n - k)!
여기서 n은 집합의 크기이고, k는 선택할 그룹의 크기다. 예를 들어, P(5, 3) = 5! / (5 - 3)! = 120 / 2 = 60이다.
이전의 factorial() 함수를 사용해 구현할 수 있지만 문제가 있다. factorial(20)은 계산할 수 있는 가장 큰 수이므로, 예를 들어 P(21, 3)을 계산할 수 없다.
더 큰 수를 다룰 수 있는 알고리즘은 다음과 같다:
func permutations(_ n: Int, _ k: Int) -> Int {
var n = n
var answer = n
for _ in 1..<k {
n -= 1
answer *= n
}
return answer
}실행해 보자:
permutations(5, 3) // 60을 반환
permutations(50, 6) // 11441304000을 반환
permutations(9, 4) // 3024을 반환이 함수는 다음과 같은 대수적 사실을 활용한다:
9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
P(9, 4) = --------------------------------- = 9 * 8 * 7 * 6 = 3024
5 * 4 * 3 * 2 * 1
분모가 분자의 일부를 상쇄시키므로 나눗셈을 수행할 필요가 없고, 중간 결과가 너무 커질 위험도 없다.
그러나 여전히 계산할 수 있는 범위에는 한계가 있다. 예를 들어, 30개의 객체로 이루어진 집합에서 15개의 그룹을 만드는 경우의 수인 P(30, 15)는 엄청나게 크기 때문에 Swift에서 처리할 수 없다. 조합론은 이렇게 재미있는 결과를 낳는다.
지금까지 주어진 컬렉션에 대해 얼마나 많은 순열이 존재하는지 세어봤다. 하지만 실제로 이 모든 순열을 어떻게 생성할 수 있을까?
Niklaus Wirth가 제안한 재귀 알고리즘은 다음과 같다:
func permuteWirth<T>(_ a: [T], _ n: Int) {
if n == 0 {
print(a) // 현재 순열을 출력
} else {
var a = a
permuteWirth(a, n - 1)
for i in 0..<n {
a.swapAt(i, n)
permuteWirth(a, n - 1)
a.swapAt(i, n)
}
}
}이 함수는 다음과 같이 사용한다:
let letters = ["a", "b", "c", "d", "e"]
permuteWirth(letters, letters.count - 1)이 코드는 입력 배열의 모든 순열을 디버그 출력에 표시한다:
["a", "b", "c", "d", "e"]
["b", "a", "c", "d", "e"]
["c", "b", "a", "d", "e"]
["b", "c", "a", "d", "e"]
["a", "c", "b", "d", "e"]
...이전에 살펴봤듯이, 총 120개의 순열이 생성된다.
이 알고리즘은 어떻게 동작할까? 좋은 질문이다! 세 개의 엘리먼트로 구성된 간단한 예제를 통해 살펴보자. 입력 배열은 다음과 같다:
[ "x", "y", "z" ]
이 배열로 함수를 호출한다:
permuteWirth([ "x", "y", "z" ], 2)n 매개변수는 배열의 엘리먼트 개수보다 하나 작은 값이다!
permuteWirth()를 호출하면 즉시 n = 1로 재귀적으로 자기 자신을 호출한다. 그리고 다시 n = 0으로 재귀 호출을 한다. 호출 트리는 다음과 같다:
permuteWirth([ "x", "y", "z" ], 2)
permuteWirth([ "x", "y", "z" ], 1)
permuteWirth([ "x", "y", "z" ], 0) // ["x", "y", "z"]를 출력n이 0이 되면 현재 배열을 출력한다. 이 시점에서 배열은 여전히 변경되지 않았다. 재귀가 기본 사례에 도달했으므로, 이제 한 단계 위로 돌아가서 for 루프에 진입한다.
permuteWirth([ "x", "y", "z" ], 2)
permuteWirth([ "x", "y", "z" ], 1) <--- 이 단계로 돌아옴
a[0]과 a[1]을 교환
permuteWirth([ "y", "x", "z" ], 0) // ["y", "x", "z"]를 출력
a[0]과 a[1]을 다시 교환이 과정에서 "y"와 "x"를 교환하고 결과를 출력했다. 이 재귀 단계에서 작업을 마치고 상위 단계로 돌아간다. 이번에는 n = 2이므로 for 루프를 두 번 반복한다. 첫 번째 반복은 다음과 같다:
permuteWirth([ "x", "y", "z" ], 2) <--- 이 단계로 돌아옴
a[0]과 a[2]를 교환
permuteWirth([ "z", "y", "x" ], 1)
permuteWirth([ "z", "y", "x" ], 0) // ["z", "y", "x"]를 출력
a[0]과 a[1]을 교환
permuteWirth([ "y", "z", "x" ], 0) // ["y", "z", "x"]를 출력
a[0]과 a[1]을 다시 교환
a[0]과 a[2]를 다시 교환두 번째 반복은 다음과 같다:
permuteWirth([ "x", "y", "z" ], 2)
a[1]과 a[2]를 교환 <--- 루프의 두 번째 반복
permuteWirth([ "x", "z", "y" ], 1)
permuteWirth([ "x", "z", "y" ], 0) // ["x", "z", "y"]를 출력
a[0]과 a[1]을 교환
permuteWirth([ "z", "x", "y" ], 0) // ["z", "x", "y"]를 출력
a[0]과 a[1]을 다시 교환
a[1]과 a[2]를 다시 교환요약하면, 먼저 다음 항목들을 교환한다:
[ 2, 1, - ]
그 다음에는 다음 항목들을 교환한다:
[ 3, -, 1 ]
재귀적으로 다시 처음 두 항목을 교환한다:
[ 2, 3, - ]
그런 다음 한 단계 위로 돌아가서 다음 항목들을 교환한다:
[ -, 3, 2 ]
마지막으로 처음 두 항목을 다시 교환한다:
[ 3, 1, - ]
물론 배열이 클수록 더 많은 교환이 발생하고 재귀도 더 깊어진다.
위 설명이 여전히 명확하지 않다면, 플레이그라운드에서 직접 시도해보길 권한다. 플레이그라운드는 이런 목적에 매우 적합하다. :-)
재미로, Robert Sedgewick가 제안한 또 다른 알고리즘을 소개한다:
func permuteSedgewick(_ a: [Int], _ n: Int, _ pos: inout Int) {
var a = a
pos += 1
a[n] = pos
if pos == a.count - 1 {
print(a) // 현재 순열을 출력
} else {
for i in 0..<a.count {
if a[i] == 0 {
permuteSedgewick(a, i, &pos)
}
}
}
pos -= 1
a[n] = 0
}이 함수는 다음과 같이 사용한다:
let numbers = [0, 0, 0, 0]
var pos = -1
permuteSedgewick(numbers, 0, &pos)배열은 처음에 모두 0으로 초기화되어야 한다. 0은 재귀의 각 단계에서 추가 작업이 필요함을 나타내는 플래그로 사용된다.
Sedgewick 알고리즘의 출력은 다음과 같다:
[1, 2, 3, 0]
[1, 2, 0, 3]
[1, 3, 2, 0]
[1, 0, 2, 3]
[1, 3, 0, 2]
...이 알고리즘은 숫자만 다룰 수 있지만, 이 숫자는 실제로 순열을 생성하려는 배열의 인덱스로 사용할 수 있으므로 Wirth의 알고리즘만큼 강력하다.
이 알고리즘이 어떻게 동작하는지 직접 파악해보자!
조합은 순서가 중요하지 않은 순열과 유사하다. 다음은 k, l, m 세 글자로 만든 여섯 가지 순열이다. 하지만 이들은 모두 같은 조합으로 간주된다:
k, l, m k, m, l m, l, k
l, m, k l, k, m m, k, l
따라서 크기가 3인 조합은 단 하나뿐이다. 하지만 크기가 2인 조합을 찾는다면 세 가지를 만들 수 있다:
k, l (l, k와 동일)
l, m (m, l와 동일)
k, m (m, k와 동일)
C(n, k) 함수는 n개의 가능성 중에서 k개를 선택하는 방법의 수를 계산한다. 이 때문에 "n-choose-k"라고도 부른다. (이 숫자를 수학적으로는 "이항 계수"라고 한다.)
C(n, k)의 공식은 다음과 같다:
n! P(n, k)
C(n, k) = ------------- = --------
(n - k)! * k! k!
보듯이, 이 공식은 P(n, k)의 공식에서 유도할 수 있다. 항상 순열의 수가 조합보다 많다. k!개의 순열이 같은 조합을 생성하므로 순열의 수를 k!로 나눈다.
앞서 k, l, m의 순열 수가 6임을 보였지만, 이 중 두 글자만 선택하면 조합의 수는 3이 된다. 공식을 사용하면 같은 답을 얻을 수 있다. 3개 중 2개를 선택하므로 C(3, 2)를 계산한다.
3 * 2 * 1 6
C(3, 2) = --------- = --- = 3
1! * 2! 2
다음은 C(n, k)를 계산하는 간단한 함수이다:
func combinations(_ n: Int, choose k: Int) -> Int {
return permutations(n, k) / factorial(k)
}이 함수를 다음과 같이 사용한다:
combinations(28, choose: 5) // 98280 출력이 함수는 내부적으로 permutations()와 factorial() 함수를 사용하므로, 이들 함수가 계산할 수 있는 숫자 크기에 제한을 받는다. 예를 들어, combinations(30, 15)는 "단지" 155,117,520이지만, 중간 결과가 64비트 정수에 맞지 않아 계산할 수 없다.
C(n, k)를 O(k) 시간과 O(1) 추가 공간으로 계산하는 더 빠른 방법이 있다. 이 방법은 C(n, k)의 공식을 다음과 같이 변형한다:
n! n * (n - 1) * ... * 1
C(n, k) = ------------- = ------------------------------------------
(n - k)! * k! (n - k) * (n - k - 1) * ... * 1 * k!
분수를 약분하면 다음 공식을 얻는다:
n * (n - 1) * ... * (n - k + 1) (n - 0) * (n - 1) * ... * (n - k + 1)
C(n, k) = --------------------------------------- = -----------------------------------------
k! (0 + 1) * (1 + 1) * ... * (k - 1 + 1)
이 공식을 다음과 같이 구현할 수 있다:
func quickBinomialCoefficient(_ n: Int, choose k: Int) -> Int {
var result = 1
for i in 0..<k {
result *= (n - i)
result /= (i + 1)
}
return result
}이 알고리즘은 이전 방법보다 더 큰 숫자를 생성할 수 있다. 전체 분자를 계산한 다음 팩토리얼로 나누는 대신, 각 단계에서 나누기 때문에 중간 결과가 훨씬 느리게 증가한다.
이 개선된 알고리즘을 다음과 같이 사용한다:
quickBinomialCoefficient(8, choose: 2) // 28 출력
quickBinomialCoefficient(30, choose: 15) // 155117520 출력이 새로운 방법은 꽤 빠르지만, 여전히 숫자 크기에 제한이 있다. C(30, 15)는 문제없이 계산할 수 있지만, C(66, 33) 같은 경우는 분자에서 정수 오버플로우가 발생한다.
팩토리얼 계산과 나누기를 피하기 위해 동적 프로그래밍을 사용하는 알고리즘이 있다. 이 알고리즘은 파스칼의 삼각형을 기반으로 한다:
0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1
6: 1 6 15 20 15 6 1
다음 행의 각 숫자는 이전 행의 두 숫자를 더해 만든다. 예를 들어, 행 6의 숫자 15는 행 5의 5와 10을 더해 만든다. 이 숫자들은 이항 계수라고 불리며, C(n, k)와 같다.
예를 들어, 행 6의 경우:
C(6, 0) = 1
C(6, 1) = 6
C(6, 2) = 15
C(6, 3) = 20
C(6, 4) = 15
C(6, 5) = 6
C(6, 6) = 1
다음 코드는 파스칼의 삼각형을 계산하여 원하는 C(n, k)를 찾는다:
func binomialCoefficient(_ n: Int, choose k: Int) -> Int {
var bc = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
for i in 0...n {
bc[i][0] = 1
bc[i][i] = 1
}
if n > 0 {
for i in 1...n {
for j in 1..<i {
bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j]
}
}
}
return bc[n][k]
}이 알고리즘은 매우 간단하다: 첫 번째 루프는 삼각형의 바깥쪽 가장자리에 1을 채운다. 다른 루프들은 이전 행의 두 숫자를 더해 삼각형의 각 숫자를 계산한다.
이제 C(66, 33)를 문제없이 계산할 수 있다:
binomialCoefficient(66, choose: 33) // 매우 큰 숫자 출력이러한 순열과 조합을 계산하는 이유가 무엇인지 궁금할 수 있다. 하지만 많은 알고리즘 문제는 사실 조합론 문제로 위장되어 있다. 종종 데이터의 모든 가능한 조합을 살펴보며 올바른 해결책을 찾아야 할 때가 있다. 만약 n!개의 잠재적 해결책을 탐색해야 한다면, 다른 접근 방식을 고려해야 한다. 이 숫자들은 매우 빠르게 커지기 때문이다!
Wirth와 Sedgewick의 순열 알고리즘, 그리고 순열과 조합을 계산하는 코드는 1993년 6월 Dr.Dobb's Magazine의 Algorithm Alley 칼럼을 기반으로 한다. 동적 프로그래밍을 사용한 이항 계수 알고리즘은 Skiena의 The Algorithm Design Manual에서 가져왔다.
Swift Algorithm Club을 위해 Matthijs Hollemans와 Kanstantsin Linou가 작성함