순열과 조합

순열

$ _nP_r : \frac{n!}{(n-r)!} $

서로 다른 원소를 가진 집합에서 대상들을 선택하여 순서 있게 배열하는 것

 

설계

단순히 $ _nP_r $ 을 구하고 싶다면 위의 공식을 이용해서 코드를 짜면 된다.

다만 유의할 점은 팩토리얼은 n이 조금만 커져도 수가 매우 커지기 때문에 위의 식 그대로 보다는 정리된 식을 사용하는 것이 효율적이다.

 

long long permutation (int n, int r) {
  long long result = 1;
  
  for (int i = n; i > n-r; i--) {
    result *= i;
  }
  
  return result;
}

 

혹은 재귀로 나타낼 수도 있다.

long long permutation (int n, int r) {
    if (r == 0) return 1;
    else return n * permutation(n-1, r-1);
}

 

 

$ _nP_r $의 모든 경우의 수를 출력하고 싶은 경우- backtracking

 

#include <iostream>
#include <vector>

using namespace std;

int n, r;
vector <int> list;

int visit[100];

void permutation(int depth) {
    if (depth == r) {
        for (int i = 0; i < r; i++)
            cout << list[i] << " ";

        cout << "\n";
        return;
    }
    
   for (int i = 1; i <= n; i++) {
       if (!visit[i]) {
            list.push_back(i);
            visit[i] = 1;
            permutation(depth+1);
            list.pop_back();
            visit[i] = 0;
        }
    }
}

int main() {
    cin >> n >> r;

    permutation(0);
    return 0;
}

 

 

 

 

중복순열

$ _n\Pi_r: n^r $

 

long long permutation_dup (int n, int r) {
    return pow(n, r);
}

 

$ _n\Pi_r $의 모든 경우의 수를 출력하고 싶은 경우- backtracking

 

#include <iostream>
#include <vector>

using namespace std;

int n, r;
vector <int> list;

void permutation_dup(int depth) {
    
    if (depth == r) {
        for (int i = 0; i < r; i++)
            cout << list[i] << " ";

        cout << "\n";
        return;
    }
    

   for (int i = 1; i <= n; i++) {
            list.push_back(i);
            permutation_dup(depth+1);
            list.pop_back();
    }
}

int main() {
    cin >> n >> r;

    permutation_dup(0);
    return 0;
}

 

 

 

 

조합

$ _nC_r: \frac{n!}{r!(n-r)!} $

서로 다른 원소를 가진 집합에서 원소들을 택하여 만든 부분집합

 

long long combination (int n, int r) {

  int nn = 1, rr = 1;
  
  for (int i = n; i > r; i--) {
    nn *= i;
    rr *= i-r; 
  }
  
  return nn/rr;
}

 

재귀로 구하는 경우 순열에서 구한 값을 $ (n-r)! $ 로 나누어주면 된다.

long long combination (int n, int r) {
	long long c = 1;
    
	for (int i = 1; i <= r; i++)
    	c *= i;
        
    return permutation(n, r) / c;
}

 

 

 

$ _nC_r $의 모든 경우의 수를 출력하고 싶은 경우 - backtracking

 

#include <iostream>
#include <vector>

using namespace std;

int n, r;
vector <int> list;

void combination(int depth, int index) {
    
    if (depth == r) {
        for (int i = 0; i < r; i++)
            cout << list[i] << " ";

        cout << "\n";
        return;
    }
    

   for (int i = index; i <= n; i++) {
            list.push_back(i);
            combination(depth+1, i+1);
            list.pop_back();
    }
}

int main() {
    cin >> n >> r;

    combination(0, 1);
    return 0;
}

 

 

 

중복조합

$ _nH_r = _{n+(r-1)}C_r $

 

long long combination_dup (int n, int r) {

  int nn = 1, rr = 1;
  n = n+r-1;
  
  for (int i = n; i > r; i--) {
    nn *= i;
    rr *= i-r; 
  }
  
  return nn/rr;
}

 

 

중복조합의 공식 유도

 

중복조합은 r개의 원소들을 순서에 상관없이 나열하는 것이므로, r개의 빈칸에 중복을 허용하여 n개의 원소를 넣는 경우의 수를 계산하는 문제와 같다. 여기에 n 가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 구분해야 하므로, n-1 개의 칸막이를 두고 n 가지 경우를 임의의 순서로 배열한다고 할 수 있다.

예를 들어 칸막이 기호를 /로 나타낸다면, 원소 A, B, C를 중복하여 5개를 뽑는 경우 중 " A A A B C "는 " A A A / B / C ", " B B B C C "는 " / B B B / C C "로 구분하는 것이다.

즉, 중복조합은 r개의 빈칸과 칸막이의 수 n-1개를 합한 r+n-1개의 빈칸에 칸막이가 들어갈 n-1개의 칸을 선택하면 된다. 결국 중복조합은 $ _{n+r−1}C_{n−1} $ 이 된다. 따라서 $_nC_r = _nC_{n−r}$이므로 $ _nH_r = _{n+r−1}C_r $ 이 된다.

 

 

$ _nH_r $의 모든 경우의 수를 출력하고 싶은 경우 - backtracking

 

#include <iostream>
#include <vector>

using namespace std;

int n, r;
vector <int> list;

void combination_dup(int depth, int index) {
    
    if (depth == r) {
        for (int i = 0; i < r; i++)
            cout << list[i] << " ";

        cout << "\n";
        return;
    }
    

   for (int i = index; i <= n; i++) {
            list.push_back(i);
            combination_dup(depth+1, i);
            list.pop_back();
    }
}

int main() {
    cin >> n >> r;

    combination_dup(0, 1);
    return 0;
}