[ C/C++] 순열(Permutation)과 조합(Combination) 알고리즘 구현하기

1. 순열 알고리즘

순열(Permutation)은 서로 다른 n 개의 대상에서 r개를 뽑아 일렬로 배열한 것을 말하고(순서 고려), 그 경우의 수는 nPr으로 표현합니다(n은 r보다 커야 합니다). 그리고 n 과 r 이 같을 때 순열의 경우의 수는 팩토리얼(factorial, n!)이 됩니다. 그리고 순열의 공식은 다음과 같습니다.

 

#include<stdio.h>

int arr[4] = { 1,2,3,4 };
int A[4];
int B[4];

void swap(int* first, int* second) {
	int temp = *first;
	*first = *second;
	*second = temp;
}

void permutation(int N, int R, int q)
{

	if (R == 0) {
		for (int i = 0; i < q; i++)
		{
			printf("%d ", B[i]);
		}
		printf("\n");
		return;
	}


	for (int i = N - 1; i >= 0; i--) 
	{
		swap(&arr[i], &arr[N - 1]);
		B[R - 1] = arr[N - 1];
		permutation(N - 1, R - 1, q);
		swap(&arr[i], &arr[N - 1]);
	}
}


int main(void)
{
	int N = 4;
	int R = 3;

	permutation(N, R, R);

	return 0;
}

4개의 대상중 3개의 순서를 정하는 경우 4*3*2 = 24가지 이며 위와 같이 출력됩니다.

 

2. 조합 알고리즘

순열과 달리, 조합(Combination)은 같은 n개의 대상 중에 r개를 뽑는데 순서를 고려하지 않습니다. n개의 대상 중에 r개를 뽑는 조합의 경우의 수는 다음과 같습니다.

여기서 조합의 점화식을 살펴보면 아래와 같은 식을 볼 수 있는데 예를들자면 원소가 A,B,C 에서 2개를 골라내는 조합을 구한다고 가정합시다. 그렇다면 (A,B) (A,C) (B,C) 3가지 경우가 나오는데 경우들을 분류를 하면

 

1. 첫번째 원소가 'A' 인 경우 (A,X)

2. 첫번째 원소가 'A'가 아닌경우 (X,X) 

두가지로 나뉘게 됩니다.

 

첫번째 경우는 첫번째 원소가 'A' 이므로, 나머지 것만 구하면 됩니다.(n-1Cr-1, n-1개중 r-1개를 조합)

두번째 경우는 첫번째 원소가 'A' 가 아니므로,  첫번째 원소까지 결정해주어야 합니다 (n-1Cr, n-1개중 r개를 조합)

즉, 2번째 분류에서 'A'가 들어가면 안되므로 2개중에 2개를 조합하는 경우의 수=>₂C₂=1=>(B,C)만이 성립하게 됩니다.

이 두개의 경우를 더하면 최종적으로 nCr 이 나오게 됩니다.

코드는 아래의 점화식과 재귀를 통해 구현하였습니다.

 

#include<stdio.h>

int arr[4] = { 1,2,3,4 };
int A[4];
int B[4];


void combination(int N, int R, int q)
{
	if (R == 0)
	{
		for (int i = q-1; i >= 0; i--)
		{
			printf("%d ", A[i]);
		}
		printf("\n");
	}
	else if (N < R)
	{
		return;
	}
	else
	{
		A[R - 1] = arr[N - 1];
		combination(N - 1, R - 1, q);
		combination(N - 1, R, q);
	}


}

int main(void)
{
	int N = 4;
	int R = 3;

	//permutation(N, R, R);
	combination(N, R, R);

	return 0;
}

 

 

 

2-1. 조합 DFS로 구현하기

#include <iostream>
#include <algorithm>
using namespace std;

int N, R;
int check[20];

void DFS(int s, int L)
{

	if (L == R)
	{
		for (int i = 0; i < R; i++)
		{
			cout << check[i] << " ";
		}
		cout << endl;
	}
	else
	{
		for (int i = s; i < N; i++)
		{
			check[L] = i;
			DFS(i + 1, L + 1);
		}
	}
}

int main(void)
{
	cin >> N >> R;

	DFS(0, 0);

	return 0;
}