순열과 조합

순열(permutation): 순서 고려, 중복 허용하지 않음
중복순열: 순서 고려, 중복 허용
조합(combination): 순서 고려하지 않음, 중복 허용하지 않음
중복조합: 순서 고려하지 않음, 중복 허용


n 개 중에서 r 개를 뽑아

순열: 순서를 정해서
1, 2, 3
1, 3, 2
2, 1, 3
...
nPr = n!(n-r)!, nP0 은 1, nPn 은 1

중복순열: 순서를 정해서, 중복 허용
1, 1, 1
1, 1, 2
1, 1, 3
...
nTTr = n 의 r 제곱승

조합: 순서에 상관없이 (1, 2, 3, 4 중에 2 개 선택)
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

n 개 중 r 개를 선택하는 모든 조합의 경우의 수
nCr = n-1Cr-1 + n-1Cr (nC0 = 1)


중복조합: 순서에 상관없이, 중복 허용  (1,2,3,4 중에 2 개 중복 선택)
1, 1
1, 2
1, 3
1, 4
2, 2
...
nHr = n + r-1Cr
nHr = nHr-1 + n-1Hr


코드

 #include <cstdio>  
 #define REPETITION  
 int T[10]; // nPr 을 이루는 각각의 경우를 저장  
 int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
 void swap(int& i, int& j) {  
   int temp = i;  
   i = j;  
   j = temp;  
 }  
 void process(int q) {  
   int i;  
   for (i = q - 1; i >= 0; i--) {  
     printf("%d ", T[i]);  
   }  
   printf("\n");  
 }  
 void permutation(int n, int r, int q) {  
   if (r == 0) {  
     process(q);  
     return;  
   }  
   int i;  
   for (i = n - 1; i >= 0; i--) {  
     swap(data[i], data[n - 1]); // n-1 을 모든 index 와 swap 해서 다양한 순서를 만든다  
     T[r - 1] = data[n - 1];  
 #ifdef REPETITION  
     permutation(n, r - 1, q);  
 #else  
     permutation(n - 1, r - 1, q);  
 #endif  
     swap(data[i], data[n - 1]);  
   }  
 }  
 void combination(int n, int r, int q) {  
   if (r == 0) {  
     process(q);  
     return;  
   }  
 #ifdef REPETITION  
   else if (n == 0)  
 #else  
   else if (n < r)  
 #endif  
   {  
     return;  
   }  
   else {  
     T[r - 1] = data[n - 1];  
 #ifdef REPETITION  
     combination(n, r - 1, q);  
 #else  
     combination(n - 1, r - 1, q); // n-1Cr-1  
 #endif  
     combination(n - 1, r, q); // n-1Cr  
   }  
 }  
 int main() {  
   permutation(4, 3, 3);  
   combination(4, 2, 2);  
   return 0;  
 }  

정리 출처: http://hochulshin.com/permutation-composition-summary/

조금 응용하면 푸는 문제:
6603번: 로또 (https://www.acmicpc.net/problem/6603)