순열(Permutation)과 조합(Combination)

순열과 조합의 개념과 공식

순열(Permutaion)	조합(Combination)
서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.	서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합.
ex. 축구 선수 12명이 서로 인사하는 경우의 수 ex. 3개의 자연수를 이용해 만들 수 있는 3자리 자연수 ex. 다른 색의 공 3개를 순서와 관계있게 3개 뽑는 경우	ex. 다른 색의 공 7개 중 2개를 뽑는 경우의 수.

 

경우의 수를 구하는 대표적인 방법들로, 뽑는 순서가 관계가 있으면 순열, 없으면 조합이다. 

경우의 수를 구하는 다른 방법들로는 모든 경우 완전 탐색하는 브루트 포스(Brute Force) 즉, 합의 법칙 등이 존재한다.

---

순열과 조합 구현 방법

	순열(Permutation)	조합(Combination)
1	do while문과 next_permutation 함수 사용	중첩 for문 이용
2	재귀함수로 구현	재귀함수로 구현

 

대강의 개요는 이러하다. 하나씩 풀어 설명하겠다.

---

순열 구현 1 - do while문과 next_ permutation

 

우선, do-while문이란,

1++;이 ++1;를 응용하여 ++해주는 순서를 달리해, 1을 먼저 활용하고 ++를 수행하듯

do-while도 while반복을 수행하기 전 do부분을 먼저 실행한다.

• do 수행
  • while문 조건식 true이면 do 수행
  • while문 조건식 false이면 do 실행 후 탈출 (여기 다시 봐야함)

즉, while문의 동작 부분을 do 로 빼주고, 최초로 한번은 실행되도록 만든 것이 do- while문이다.

 

자세한 정리는 이 글 참고하기.

https://webclub.tistory.com/166

반복문(for문, while문, do-while문)

 

next_permutation은 오름차순 순열, prev_permutation은 내림차순 순열을 만드는 함수이다.

• next_permutation(v.begin(), v.end())
  • 첫번째 파라미터: iterator, 여기부터 순열 진행
  • 두번째 파라미터: iterator, 여기까지 순열 진행
• permutation 한번 실행하고 true 반환, 더 이상 다음 순열이 없을 때는 false 반환
  • 새로운 순열이 이전 순열보다 사전순으로 큰 경우 true
  • 마지막 순열에 도달하고 범위가 첫번째 순열로 재설정된 경우 false
• 주의점: 해당 배열의 그 다음 번째 순열을 만들어내는 함수이기 때문에 꼭 정렬한 후 사용해야 모든 경우의 수를 구할 수 있다.

 

두 가지 기본 문법을 이해하고 본격적으로 순열을 구현해보자.

#include <bits/stdc++.h>
using namespace std;

// 벡터의 모든 원소를 출력하는 함수
// &(reference)로 전달하는 이유: vector가 클 경우 복사를 막고 원본 이용하기 위해서

void printV(vector<int> &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
        cout << "\n";
    }
}

int main()
{
    int a[3] = {1, 2, 3};
    vector<int> v;

    // 배열 a의 모든 원소를 벡터 v에 집어넣음.
    for (int i = 0; i < 3; i++) v.push_back(a[i]);

    // next_permutation : 순열을 생성한 후 true, 더 이상 다음 순열이 없을 때는 false 반환
    do
    {
        printV(v);
    } while (next_permutation(v.begin(), v.end()));
    // 1. printV 수행 {1,2,3}
    // 2. next_permutation 실행 후 printV 수행 ...

    cout << "-----------" << '\n';
    // 벡터 초기화
    v.clear();


    // 배열 a의 원소를 내림 차순으로 벡터 v에 집어 넣음
    for (int i = 2; i >= 0; i--) v.push_back(a[i]);

    // 내림차순으로 순열을 뽑는다.
    do
    {
        printV(v);
    } while (prev_permutation(v.begin(), v.end()));

    return 0;
}

 

디버깅해본 것

 

정확히 로직의 순서를 다 따라가진 못했지만, 대충 몇 depth의 재귀에서 swap이 일어나고 또 반복되는 것인지 감은 온 것같다.

무한히 뻗어나가는 이미지화

---

순열 구현 2 - 재귀 함수

 

next_permutation함수를 사용하지 않고 직접 구현하는 방법

#include <bits/stdc++.h>
using namespace std;

int a[3] = {1,2,3};
int n = 3, r = 3;

// 배열 모든 원소 출력하는 함수
void print(){
    for(int i = 0; i < r; i++){
        cout << a[i] << " ";
    }
    cout << "\n";
}

// n개 중 r개를 뽑아 순서있게 나열하는 방법
// depth: 트리의 레벨이자 높이 즉, 얼마나 뻗어나가는지.
// 아래의 코드는 depth가 0~n이 될때까지 실행

void makePermutation(int n, int r, int depth){
    if(r == depth){
        print();
        return;
    }

    for(int i = depth; i < n; i++){
        swap(a[i], a[depth]);   // 순서를 swap
        makePermutation(n,r,depth+1);
        swap(a[i], a[depth]);
    }
    return;
}

int main(){

    makePermutation(n,r,0);
    return 0;

}

---

조합 구현 1 - 중첩 for 문

 

조합: 서로 다른 n 개 중 순서에 상관없이 r개를 뽑는다.

r만큼 중첩된 for문을 구현하면된다.

 

r의 개수가 3개 이하이면 for문으로 하는 것이 직관적이고 당장 떠올리기 쉬울 것.

 

서로 다른 5개 중 3개를 뽑을 때

#include <bits/stdc++.h>
using namespaces std;

int n = 5;
int k = 3;
int a[5] = {1,2,3,4,5};

int main(){
	for(int i = 0; i < n; i++){
    	for(int j = i+1; j < n; j++){
        	for(int k = j+1; k < n; k++){
            cout << i<< " " << j << " " << k <<'\n';
        }
    }
	
    return;
}

---

조합 구현 2 - 재귀 함수

 

하지만, r이 4개 이상이라면? 중첩 for문을 돌리기 힘들 수 있다.

재귀를 이용해 조합을 구현하는 방법도 알아두자.

 

서로 다른 5개 중 3개를 뽑을 때

#include <bits/stdc++.h>
using namespace std;

int n = 5, k = 3;
int a[5] = {1,2,3,4,5};

void print(vector<int> b){
    for(int i : b) cout << i << " ";
    cout << '\n';
}

void combi(int start, vector<int> b){
    if(b.size()==k){
        print(b);
        return;
    }

    for(int i = start +1; i < n; i++){
        b.push_back(i);
        combi(i,b);
        b.pop_back();
    }
    return;
}

int main(){
    vector<int> b;
    combi(-1,b);
    return 0;
}