예를 들어, 주어진 요소들로 두 개의 원소를 배열하여 만들 수 있는 모든 순열을 생성합니다.
{A, B}와 {B, A}는 각각 다른 순열로 취급됩니다.
순열에서는 요소들의 배열 순서가 중요합니다.
#include <iostream>
int sel;
int used[10];
int ch[10];
char arr[10]{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
/// <summary>
/// 중복을 무시하고 가능한 모든 경우의 수를 획득(순열)
/// </summary>
/// <param name="s"></param>
void DFS_ALL_Combinations(int s)
{
if (s == sel)
{
for (int i = 0; i < sel; ++i)
printf("%c ", arr[ch[i]]);
printf("\n");
}
else
{
for (int i = 0; i < sel; ++i)
if (!used[i])
{
used[i] = true;
ch[s] = i;
DFS_ALL_Combinations(s + 1);
used[i] = false;
}
}
}
중복을 무시하고 가능한 모든 경우의 수(순열)을 출력하는 DFS입니다.
이 함수의 시간 복잡도는 sel! (sel 팩토리얼)입니다. sel이 10이 넘어가면 사용이 불가능할정도로 수행 시간이 급격히 느려집니다.
조합(Combinations)
요소의 선택이 주요한 특징입니다.
순서는 신경 쓰지 않고, 요소들을 선택된 개수만큼 뽑아서 만들어집니다.
예를 들어, 주어진 요소들로 두 개의 원소를 선택하여 만들 수 있는 모든 조합을 생성합니다.
{A, B}와 {B, A}는 같은 것으로 취급됩니다.
조합에서는 선택된 요소들의 순서가 중요하지 않습니다.
/// <summary>
/// 중복이 없는 조합을 뽑기
/// </summary>
/// <param name="s">시작 값 start</param>
/// <param name="p">선택 원소 위치 place</param>
void DFS_Combinations(int s, int p)
{
// position이 sel(뽑아야 할 총 개수)라면?
if (p == sel)
{
for (int i = 0; i < sel; ++i)
printf("%c ", arr[ch[i]]);
printf("\n");
}
else
{
// i는 현재 선택 개수부터 시작하여 선택할 마지막 값까지 반복
for (int i = s; i < 4; ++i)
{
ch[p] = i; // s번째 선택한 값은 i번
// i + 1를 start로, p + 1을 position으로하여 다음 재귀 호출
DFS_Combinations(i + 1, p + 1);
}
}
}
