순열(Permutation) 과 조합(Combination)

1. Permutation Algorithm이란

• 순열은 주어진 요소들의 순서를 고려하여 배열하는 모든 경우의 수를 의미합니다.
• 순열은 정의역과 공역이 같은 일대일 대응입니다.
• n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값입니다.

---

2. Permutation 공식

• $_{n}\mathrm{P}_{r} = \frac{n!}{(n-r)!}$
• 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다.
• 모든 경우의 수를 계산하는 완전 탐색에서 사용되는 알고리즘입니다.

[순열 예시 -> {1 2 3}에서 2개를 뽑는 경우]
1 2
1 3
2 1
2 3
3 1
3 2

• 1 2 3과 1 3 2는 다른 값입니다.

---

3. Permutation 조건

• 순서가 중요: 선택된 요소들의 순서가 다르면 다른 경우로 간주합니다.
• 중복이 없는 순열: 일반적인 순열에서는 동일한 요소를 중복해서 사용할 수 없습니다.

---

4. Permutation 동작 방식

1. 일반 순열 : 중복 없이 주어진 요수들을 배열하는 방식입니다.

   • 일반 순열 코드 예시

   def permute(arr, start, end):
       if start == end:
           print(arr)
       else:
           for i in range(start, end + 1):
               arr[start], arr[i] = arr[i], arr[start]  # 요소 교환
               permute(arr, start + 1, end)  # 재귀 호출
               arr[start], arr[i] = arr[i], arr[start]  # 요소 복원
   
   # 사용 예시
   arr = [1, 2, 3]
   permute(arr, 0, len(arr) - 1)

2. 중복 순열: 요소를 중복해서 선택해서 선택할 수 있는 순열입니다.

   • 중복 순열 코드 예시

   import itertools
   
   arr = [1, 2, 3]
   perm = itertools.product(arr, repeat=3)
   for p in perm:
       print(p)

---

4-1. 순열 문제 예시

예시: [1,2,3]의 모든 순열 구하기

def permute(arr, start, end):
    if start == end:
        print(arr)
    else:
        for i in range(start, end + 1):
            arr[start], arr[i] = arr[i], arr[start]
            permute(arr, start + 1, end)
            arr[start], arr[i] = arr[i], arr[start]

arr = [1, 2, 3]
permute(arr, 0, len(arr) - 1)

1. 초기 호출: permute([1, 2, 3], 0, 2)에서 시작합니다.
   • start = 0, end = 2
   • 이 단계에서는 첫 번째 요소(1)를 기준으로 다른 요소들과 교환이 시작됩니다.
2. 첫 번째 재귀 호출 (1과 자기 자신 교환):
   • 1과 1을 교환하여 그대로 유지 (arr = [1, 2, 3])
   • permute([1, 2, 3], 1, 2)로 재귀 호출.
3. 두 번째 재귀 호출 (2와 자기 자신 교환):
   • 2와 2를 교환하여 그대로 유지 (arr = [1, 2, 3]).
   • permute([1, 2, 3], 2, 2)로 재귀 호출.
4. 기저 사례 도달 (출력):
   • start == end이므로 배열 [1, 2, 3]을 출력합니다.
   • 이후 스택을 따라 복귀하여 다음 교환을 시도합니다.
5. 세 번째 재귀 호출 (2와 3 교환):
   • 복귀 후, 2와 3을 교환하여 배열이 [1, 3, 2]가 됩니다.
   • permute([1, 3, 2], 2, 2)로 재귀 호출.
6. 기저 사례 도달 (출력):
   • start == end이므로 배열 [1, 3, 2]를 출력합니다.
   • 다시 복귀하여 교환을 원상태로 복원(arr = [1, 2, 3]).
7. 네 번째 재귀 호출 (1과 2 교환):
   • 1과 2를 교환하여 배열이 [2, 1, 3]가 됩니다.
   • permute([2, 1, 3], 1, 2)로 재귀 호출.
8. 이후 동일한 방식으로 순차적으로 재귀 호출 및 교환 작업이 진행됩니다. 최종적으로 [1, 2, 3]에 대한 모든 순열이 출력됩니다.

---

5. Combination Algorithm이란?

• 조합은 주어진 요소들 중에서 순서와 상관없이 일부를 선택하는 경우의 수를 의미합니다.
• 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것 입니다.

---

6. Combination 공식

• $C(n, r) = \frac{n!}{r!(n-r)!}$
• n개의 서로 다른 요소 중에서 r개의 요소를 선택하는 경우의 수입니다

[조합 예시 -> {1 2 3 4}에서 3개를 뽑는 경우]
1 2 3
1 2 4
1 3 4
2 3 4

• 1 2 3과 1 3 2은 같은 값이라고 바라보기 때문에 하나의 결과만 나오게 된다

---

7. Combination 조건

1. 순서가 중요하지 않음: 선택된 요소들의 순서가 달라도 동일한 경우로 간주합니다.
2. 중복이 없는 조합: 일반적인 조합에서는 동일한 요소를 중복해서 사용할 수 없습니다.

---

8. Combination 동작 방식

1. 일반 조합: 중복 없이 주어진 요소들 중에서 일부를 선택하는 방식입니다.

   • 일반 조합 코드 예시

   def combine(arr, n, start, chosen):
       if len(chosen) == n:
           print(chosen)
           return
       for i in range(start, len(arr)):
           combine(arr, n, i + 1, chosen + [arr[i]])
   
   arr = [1, 2, 3]
   combine(arr, 2, 0, [])

2. 중복 조합: 요소를 중복해서 선택할 수 있는 조합입니다.

   • 중복 조합 코드 예시

   import itertools
   
   arr = [1, 2, 3]
   comb = itertools.combinations_with_replacement(arr, 2)
   for c in comb:
       print(c)

---

8-1. 조합 문제 예시

예시: [1, 2, 3]에서 2개의 요소를 선택하는 모든 조합 구하기

def combine(arr, n, start, chosen):
    if len(chosen) == n:
        print(chosen)
        return
    for i in range(start, len(arr)):
        combine(arr, n, i + 1, chosen + [arr[i]])

arr = [1, 2, 3]
combine(arr, 2, 0, [])

1. 초기 호출: combine([1, 2, 3], 2, 0, [])에서 시작합니다.
   • start = 0, n = 2, chosen = []
   • 이 단계에서는 첫 번째 요소(1)를 선택하는 것이 시도됩니다.
2. 첫 번째 재귀 호출 (1 선택):
   • [1]을 선택하고, combine([1, 2, 3], 2, 1, [1])로 재귀 호출합니다.
   • start = 1, chosen = [1]
3. 두 번째 재귀 호출 (1, 2 선택):
   • [2]를 선택하여 chosen = [1, 2]가 됩니다.
   • combine([1, 2, 3], 2, 2, [1, 2])로 재귀 호출합니다.
4. 기저 사례 도달 (출력):
   • len(chosen) == n이므로 [1, 2]를 출력합니다.
   • 이후 복귀하여 다음 선택을 시도합니다.
5. 세 번째 재귀 호출 (1, 3 선택):
   • 복귀 후 [1, 3]을 선택하고, combine([1, 2, 3], 2, 3, [1, 3])로 재귀 호출합니다.
6. 기저 사례 도달 (출력):
   • len(chosen) == n이므로 [1, 3]을 출력합니다.
   • 다시 복귀하여 다음 선택을 시도합니다.
7. 네 번째 재귀 호출 (2 선택):
   • 2를 선택하고, combine([1, 2, 3], 2, 2, [2])로 재귀 호출합니다.
8. 다섯 번째 재귀 호출 (2, 3 선택):
   • [2, 3]을 선택하고, combine([1, 2, 3], 2, 3, [2, 3])로 재귀 호출합니다.
9. 기저 사례 도달 (출력):
   • len(chosen) == n이므로 [2, 3]을 출력합니다.
   • 모든 경우의 수가 다 출력되었으므로 종료합니다.

---

9. 순열과 조합의 공통점과 차이점

• 공통점
  • 수학적 기법: 둘 다 수학적으로 요소를 선택하거나 배열하는 방법을 나타냅니다.
  • 재귀적 구현: 순열과 조합 모두 재귀적으로 쉽게 구현할 수 있습니다.
• 차이점
  • 순서의 중요성
    • 순열은 순서가 중요합니다. 예를 들어 [1, 2]와 [2, 1]은 다른 순열로 간주됩니다.
    • 조합은 순서가 중요하지 않습니다. 예를 들어 [1, 2]와 [2, 1]은 동일한 조합으로 간주됩니다.
  • 경우의 수
    • 순열은 요소의 순서를 고려하기 때문에 경우의 수가 더 많습니다.
    • 조합은 순서를 고려하지 않으므로 경우의 수가 상대적으로 적습니다.