[0주차] 순열(permutation)과 조합(combination) - 순열편

 

📌 순열과 조합

 

순열(permutation)이란 ?

 

n 명중의 r명을 뽑아서 줄세우는 방법의 수를 의미한다. 

 

 

 

 

조합(combination)이란 ?

 

순서의 고려 없이 단순하게 선택만 하는 경우의 수, n 명중의 r명을 뽑기만 하는 방법의 수를 의미한다.

 

​​

 

 

4C2를 구하는 공식은 순열을 구하는 공식보다는 조금 어렵다. 아이러니하게도 조합을 구하기 위해서는 순열을 먼저 구한 후, 제거시키면 된다. (저질러놓고 취소하는 방식) 즉 4C2 = 4P2/2!  이 된다.

 

 

 

순열을 먼저 구한 후, 팩토리얼로 나누면 조합의 수를 구할 수 있다. 

 

 

 

📌 C++ 에서의 순열 next_permutation(from,to) / prev_permutation(from,to)

 

C++ 에서는 순열을 구하는 함수가 미리 준비되어 있다.  그 중 next_permutation() 함수는 정렬된 배열을 기반으로 오름차순 으로 순열을 만든다. 그에 반해 prev_permutation은 내림차순 을 기반으로 순열을 만든다.

 

우선은 next_permutation()  함수의 쓰는 방법부터 알아보자.

 

next_permutation() 의 조건 

 

• next_permutation()을 사용하려면 우선 헤더에 <algorithm> 파일을 추가해주어야한다.
•  배열이 sorting 되어 있어야 한다

 

next_permutation() 의 파라미터

 

• 우선 from은 배열의 시작을 의미한다.
• to는 배열의 마지막이 아닌 마지막 부분 다음을 파라미터로 넣어주어야한다.
• 예를 들어, 배열의 길이가 2인 배열이 있다면  next_purmuation(0,2)이 들어가 주어야 한다.

 

next_permutation() 예제 코드

 

 

 

 

코드 순서 

 

• 초기 배열: a = {1, 2, 3}. 
• 출력: 1 2 3 (for문이 첫 번째 출력문만 포함하고 있음).
• std::next_permutation을 호출해 다음 순열을 계산.
• 배열이 변경: a = {1, 3, 2}.
• 출력: 1 3 2.
• 위 과정 반복.
• 순열이 끝나면(마지막 순열: 3 2 1), 루프 종료.

 

 

next_permutation() 응용

 

지금까지 순열이 될 수 있는 3P3을 만들어보았다면 5P3처럼 모든 수가 아닌 특정 수를 뽑아서 출력해보도록 하자. 방법은 아주 간단하다.

 

 

 

• 초기 배열: a = {1, 2, 3, 4, 5}.
• 집합(set) 선언 : set<string> unique_results;
• 배열의 첫 번째 원소와 공백 그리고 두 번째 원소를 문자열로 만들어 result에 저장
• 저장된 result를 선언하여 선언하였던 집합에 원소로 추가 
• 위 과정 반복
• 중복 제거된 집합들의 원소를 출력 후 개행 

 

📌 재귀함수로 만드는 순열

 

단순히 라이브러리로 구현된 함수로 순열을 만드는 것은 어렵지 않았지만, 직접 순열 함수를 만드는 것은 생각보다 어려웠다.

그 이유는 반복문 안에 재귀함수를 입력해야했던 것과 동적인 인덱스 때문이었던 것 같다. 코드는 다음과 같다.

 

 

📌 Pseudo Code 

1) 기저사례 : 깊이가 조합하려는 수가 같다면 -> if(depth == k) 

2) 배열의 깊이부터 n 만큼 반복 -> for (int i = depth; i < n; i++)

2-1) i번째 요소와 depth 번째 요소를 교환 -> swap(a[i],a[depth]

2-2) 재귀 함수 호출 -> permutation(depth+1)

2-3) 원상 복구  -> swap(a[i]) , a[depth])

 

 

여기서 주목해야할 점은 makePrmutation의 함수 부분이고, 그 중에서도 반복문과 재귀함수이다.

다음은 C++ 백트래킹 코드가 n = 3, r = 3일 때 처음부터 끝까지 어떻게 순차적으로 호출되고 반환되는지, 총 31단계에 걸쳐 끊김 없이 정리한 흐름이다. 

 

전체 흐름 (세부 단계)

1) 호출: f(3, 3, 0)

• depth = 0, 현재 v = [0, 1, 2]
• for(i = 0 ~ 2)

2) (정방향 swap, i=0)

• 실행: swap(v[0], v[0])
  • 벡터: 여전히 [0, 1, 2]
• 재귀 호출: f(3, 3, 1)

---

3) 호출: f(3, 3, 1)

• depth = 1, 현재 v = [0, 1, 2]
• for(i = 1 ~ 2)

4) (정방향 swap, i=1)

• 실행: swap(v[1], v[1])
  • 벡터: [0, 1, 2](변화 없음)
• 재귀 호출: f(3, 3, 2)

---

5) 호출: f(3, 3, 2)

• depth = 2, 현재 v = [0, 1, 2]
• for(i = 2 ~ 2) → 유일한 반복 i=2

6) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [0, 1, 2](변화 없음)
• 재귀 호출: f(3, 3, 3)

---

7) 호출: f(3, 3, 3)

• depth = 3, r = 3 → 기저 조건 충족
  • 순열 출력: [0, 1, 2]
• 재귀 반환

---

8) 복귀: f(3, 3, 2)

• 이제 역방향 swap: swap(v[2], v[2])
  • 벡터: [0, 1, 2](변화 없음)
• i=2 반복 끝, for 문 종료
• 함수 f(3,3,2) 반환

---

9) 복귀: f(3, 3, 1)

• 방금 i=1 처리 완료
• 역방향 swap: swap(v[1], v[1])
  • 벡터: [0, 1, 2]
• for 문에서 다음 i=2 진행

10) (정방향 swap, i=2, depth=1)

• 실행: swap(v[2], v[1])
  • 벡터: [0, 2, 1] (인덱스 1,2 교환)
• 재귀 호출: f(3, 3, 2)

---

11) 호출: f(3, 3, 2)

• depth = 2, 현재 v = [0, 2, 1]
• for(i = 2 ~ 2)

12) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [0, 2, 1](변화 없음)
• 재귀 호출: f(3, 3, 3)

---

13) 호출: f(3, 3, 3)

• 기저 조건 충족 → 출력: [0, 2, 1]
• 재귀 반환

---

14) 복귀: f(3, 3, 2)

• 역방향 swap: swap(v[2], v[2])
  • 벡터: [0, 2, 1](변화 없음)
• i=2 끝, for 문 종료
• 함수 f(3,3,2) 반환

---

15) 복귀: f(3, 3, 1)

• 방금 i=2 처리 완료
• 역방향 swap: swap(v[2], v[1])
  • 벡터: [0, 1, 2]
• 이제 i=1,2 모두 처리 → for 문 종료
• 함수 f(3,3,1) 반환

---

16) 복귀: f(3, 3, 0)

• 방금 i=0 처리 완료
  (정확히 말하면, i=0 블록 + 그 안에서 i=1,2까지 다 끝난 것이고, 함수가 돌아온 상태)
• 역방향 swap: swap(v[0], v[0])
  • 벡터: [0, 1, 2](변화 없음)
• for 문에서 다음 i=1 진행

17) (정방향 swap, i=1, depth=0)

• 실행: swap(v[1], v[0])
  • 벡터: [1, 0, 2] (인덱스 0,1 교환)
• 재귀 호출: f(3, 3, 1)

---

18) 호출: f(3, 3, 1)

• depth = 1, 현재 v = [1, 0, 2]
• for(i = 1 ~ 2)

19) (정방향 swap, i=1)

• 실행: swap(v[1], v[1])
  • 벡터: [1, 0, 2](변화 없음)
• 재귀 호출: f(3, 3, 2)

---

20) 호출: f(3, 3, 2)

• depth = 2, 현재 v = [1, 0, 2]
• for(i = 2 ~ 2)

21) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [1, 0, 2](변화 없음)
• 재귀 호출: f(3, 3, 3)

---

22) 호출: f(3, 3, 3)

• 기저 조건 충족 → 출력: [1, 0, 2]
• 재귀 반환

---

23) 복귀: f(3, 3, 2)

• 역방향 swap: swap(v[2], v[2])
  • 벡터: [1, 0, 2]
• i=2 끝, for 문 종료
• 함수 f(3,3,2) 반환

---

24) 복귀: f(3, 3, 1)

• 방금 i=1 처리 완료
• 역방향 swap: swap(v[1], v[1])
  • 벡터: [1, 0, 2](변화 없음)
• 다음 i=2

25) (정방향 swap, i=2, depth=1)

• 실행: swap(v[2], v[1])
  • 벡터: [1, 2, 0] (인덱스 1,2 교환)
• 재귀 호출: f(3, 3, 2)

---

26) 호출: f(3, 3, 2)

• depth = 2, 현재 v = [1, 2, 0]
• for(i = 2 ~ 2)

27) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [1, 2, 0](변화 없음)
• 재귀 호출: f(3, 3, 3)

---

28) 호출: f(3, 3, 3)

• 기저 조건 충족 → 출력: [1, 2, 0]
• 재귀 반환

---

29) 복귀: f(3, 3, 2)

• 역방향 swap: swap(v[2], v[2])
  • 벡터: [1, 2, 0]
• for 문 종료
• 함수 f(3,3,2) 반환

---

30) 복귀: f(3, 3, 1)

• 방금 i=2 처리 완료
• 역방향 swap: swap(v[2], v[1])
  • 벡터: [1, 0, 2]
• i=1,2 끝 → for 문 종료
• 함수 f(3,3,1) 반환

---

31) 복귀: f(3, 3, 0)

• 방금 i=1 처리 완료
• 역방향 swap: swap(v[1], v[0])
  • 벡터: [0, 1, 2]
• 다음 i=2

32) (정방향 swap, i=2, depth=0)

• 실행: swap(v[2], v[0])
  • 벡터: [2, 1, 0]
• 재귀 호출: f(3, 3, 1)

---

33) 호출: f(3, 3, 1)

• depth = 1, 현재 v = [2, 1, 0]
• for(i = 1 ~ 2)

34) (정방향 swap, i=1)

• 실행: swap(v[1], v[1])
  • 벡터: [2, 1, 0](변화 없음)
• 재귀 호출: f(3, 3, 2)

---

35) 호출: f(3, 3, 2)

• depth = 2, v = [2, 1, 0]
• for(i = 2 ~ 2)

36) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [2, 1, 0](변화 없음)
• 재귀 호출: f(3, 3, 3)

---

37) 호출: f(3, 3, 3)

• 기저 조건 충족 → 출력: [2, 1, 0]
• 재귀 반환

---

38) 복귀: f(3, 3, 2)

• 역방향 swap: swap(v[2], v[2])
  • 벡터: [2, 1, 0]
• i=2 끝, for 문 종료
• 함수 f(3,3,2) 반환

---

39) 복귀: f(3, 3, 1)

• 방금 i=1 처리 완료
• 역방향 swap: swap(v[1], v[1])
  • 벡터: [2, 1, 0](변화 없음)
• 다음 i=2

40) (정방향 swap, i=2, depth=1)

• 실행: swap(v[2], v[1])
  • 벡터: [2, 0, 1]
• 재귀 호출: f(3, 3, 2)

---

41) 호출: f(3, 3, 2)

• depth = 2, 현재 v = [2, 0, 1]
• for(i = 2 ~ 2)

42) (정방향 swap, i=2)

• 실행: swap(v[2], v[2])
  • 벡터: [2, 0, 1]
• 재귀 호출: f(3, 3, 3)

---

43) 호출: f(3, 3, 3)

• 기저 조건 충족 → 출력: [2, 0, 1]
• 재귀 반환

---

44) 복귀: f(3, 3, 2)

• 역방향 swap: swap(v[2], v[2])
  • 벡터: [2, 0, 1]
• i=2 끝, for 문 종료
• 함수 f(3,3,2) 반환

---

45) 복귀: f(3, 3, 1)

• 방금 i=2 처리 완료
• 역방향 swap: swap(v[2], v[1])
  • 벡터: [2, 1, 0]
• i=1,2 끝, for 문 종료
• 함수 f(3,3,1) 반환

---

46) 복귀: f(3, 3, 0)

• 방금 i=2 처리 완료
• 역방향 swap: swap(v[2], v[0])
  • 벡터: [0, 1, 2]
• 이제 i=0,1,2 모두 처리 → for 문 종료
• 함수 f(3,3,0) 완전 종료

---

최종 출력 순서

중간에 기저 조건에서 출력된 순열을 순서대로 적어 보면:

1. [0, 1, 2]
2. [0, 2, 1]
3. [1, 0, 2]
4. [1, 2, 0]
5. [2, 1, 0]
6. [2, 0, 1]

(총 6가지, 3!3!3!개)

---

요약

• 각 depth마다 i = depth부터 i < n까지 반복을 수행하며, swap -> 재귀 -> swap(원상복구) 형태로 진행된다.
• depth(깊이) = r(선택할 원소 개수) 에 도달하면 기저 조건이 충족되어 순열을 출력하고 재귀를 반환한다.
• 반환 시에는 반드시 원상복구를 통해 벡터가 이전 상태로 돌아가야한다.
• 이렇게 해서 개의 순열(6개)이 모두 출력되고, 최종 46번째 단계에서 초기 호출 f(3, 3, 0)의 반복문도 종료되면서 모든 재귀가 마무리된다.

 

 

📌 응용 : 3P2를 뽑고 싶을 땐 어떻게 하지 ?

 

 

 

아주 간단하게 출력 시에 길이(r)만큼만 출력해주면 된다. 하지만 이것은 3P2일 경우이고 5P2일 경우, 중복 출력 문제를 해결해야 하는데 이러한 문제는 set 자료구조를 활용함으로써 해결할 수 있다.