[C++] 순열, 조합, 중복순열, 중복조합 구현

문제를 풀다보면 종종 순열, 조합, 중복순열, 중복조합을 이용하는 경우가 있다.

이번 포스팅에서는 각각의 정의와 c++로 구현하는 방법에 대해 정리해보았다.

 

1. 순열

---

: 순서를 따지고, 중복을 허용하지 않는다.

중복을 허용하지 않기 때문에, 중복을 검사하는 visitied 처리가 필요하다.

depth로 r만큼의 길이를 출력해준다.

그렇지 않다면 중복을 검사한 후, 재귀로 함수를 부른다.

depth가 r이 될때, 순열이 완성된 것이므로, 순열을 출력해주고 backtracking해준다.

backtracking을 수행한 뒤, check[i] = false로 다음 루프에서 해당 숫자를 사용할 수 있게 한다.

그렇지 않으면, 한번 사용된 숫자는 계속 사용중으로 표시가 되어, 그 숫자가 다른 가능한 순열 위치에서 사용될 수 없다.

 

int depth = 0;
int arr[r] = {0,}; //nPr
bool check[n+1] = {false,};

void permutation(int depth)
{
	if(depth == r) {
    	for(int i=0; i<r; i++) {
        	cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=1; i<=n; i++) {
    	if(!check[i]) {
        	check[i] = true;
            arr[depth] = i;
            permutation(depth+1);
            check[i] = false;
        }
    }
}

 

 

2. 조합

---

: 순서를 따지지 않고, 중복을 허용하지 않는다.

순서, 중복을 허용하지 않기 때문에 시작값을 정해주어야 한다. 시작값은 이전에 선택한 값+1이다.

void combination(int start, int depth)
{
	if(depth==r) {
    	for(int i=0; i<r; i++) {
        	cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=start; i<=n; i++) {
    	arr[depth] = i;
        combination(i+1, depth+1);
    }
}

 

 

 

 

3. 중복 순열

---

: 순서를 따지고, 중복을 허용한다.

중복검사를 뺀 순열 코드와 동일하다.

 

int depth = 0;
int arr[r] = {0,}; //nPr

void permutation(int depth)
{
	if(depth == r) {
    	for(int i=0; i<n; i++) {
        	cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=1; i<=n; i++) {
    	arr[depth] = i;
        permutation(depth+1);

    }
}

 

 

 

 

4. 중복 조합

---

: 순서를 따지지 않고, 중복을 허용한다.

조합 코드와 동일하지만, 반복문의 시작값을 이전에 선택한 값으로 해준다.

 

void combination(int start, int depth)
{
	if(depth==r) {
    	for(int i=0; i<r; i++) {
        	cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=start; i<=n; i++) {
    	arr[depth] = i;
        combination(i, depth+1);
    }
}

 

 

< 정리 표 >

	정의	시작값 여부
순열	순서 O 중복 X	X
조합	순서 X 중복 X	X
중복 순열	순서 O 중복 O	O
중복 조합	순서 X 중복 O	O