[Algorithm] 순열(Permutation) 구현 코드

인트로

본 포스팅에선 순열을 구하는 코드를 소개하려 한다. 결론부터 말하면 재귀 함수(DFS)로 순열을 구할 수 있다.

 

순열이란 n개 중에 r개를 뽑아 순서 있게 나열하는 경우의 수로 다음과 같이 표현한다. $_nP_r=\frac{n!}{(n-r)!}$

이와 유사하게 순서가 없이 n개 중에 r개를 뽑는 것을 조합이라고 한다.

순열 : 코드

DFS로 순열을 구하는 코드이다.

집합의 원소 번호를 order배열에 순열의 형태로 저장하고 출력 시 arr배열의 인덱싱 용도로 사용한다.

#include <iostream>
using namespace std;

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int cnt, n, r;
int visited[4];
int order[4];

void permutation(int now)
{
	if (now == r)
	{
		for (int i = 0; i < r; i++)
		{
			cout << arr[order[i]] << " ";
		}
		cout << endl;
		cnt++;

		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (visited[i])
			continue;

		visited[i] = true;
		order[now] = i;
		permutation(now + 1);
		visited[i] = false;
	}
}

int main()
{
	cout << "n : ";
	cin >> n;
	cout << "r : ";
	cin >> r;
	cout << n << 'P' << r << endl;

	permutation(0);
	cout << "순열의 개수 : " << cnt;
}