모든조합 / 모든순열 구하기 - C#
■ 모든 조합을 구해주는 클래스
using System.Collections.Generic;
class TCombi
{
private int[] result;
private Stack<int> stack;
private int r, n;
public TCombi(int r, int n)
{ // nCr 계산
this.r = r;
this.n = n;
result = new int[r];
stack = new Stack<int>();
stack.Push(0);
}
public int[] next()
{ // null 리턴하면 더 이상 없음
while (stack.Count > 0)
{
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n)
{
result[index++] = value++;
stack.Push(value);
if (index == r)
{
return result;
}
}
}
return null;
}
}
int r = 3;
int cnt = 0;
TCombi comb = new TCombi(r, n);
while (true)
{
int[] c = comb.next();
if (c == null) break;
for (int i = 0; i < c.Length; i++)
{
// c[i]가 구해진 조합
}
}
■ 모든 순열을 구하는 방법
순열을 구하는 알고리즘은 많이 있지만 그 중 효율도 좋고, 알아보기 편한 알고리즘으로 TNHP(The Next Higher Permutation)이 있다. TNHP는 순열을 가장 작은 것부터 큰 순서대로 구해내는 방식이다. TNHP의 procedure는 다음과 같다.
n개의 서로 다른 원소를 갖는 배열이 있다고 하자. 그리고 배열의 원소들은 오름차순으로 정렬이 되어있다 (순열의 가장 작은 값이기 때문에). TNHP는 모두 4단계의 과정을 거친다.
1-step. find i.
i 값을 찾기 위해서 우선 배열의 index의 마지막부터 인접하는 두 개의 원소를 비교를 한다. 비교되는 두 개의 원소중 index가 낮은 쪽의 원소가 높은쪽의 원소보다 작다면 낮은 쪽 원소의 index의 값이 바로 i이다. i값을 찾을 때까지 배열의 처음 쪽으로 비교하는 위치를 이동한다.
2-step. find j.
j값을 찾기 위해서 우선 배열의 index의 마지막 원소부터, i가 가리키는 index의 원소와 비교를 한다. i가 가리키는 index의 원소와 현재 비교를 위해 가리키는 원소를 비교하여, 현재 원소의 값이 크면 그 index가 바로 j이다.
3-step. swap i, j
i와 j의 위치를 바꿔준다.
4-step. sorting from i+1
i+1번지부터 배열의 끝까지 오름차순으로 정렬한다.
위의 procedure를 예를 들어 설명하면 다음과 같다.
|
1 |
2 |
3 |
4 |
4개의 원소를 가진 배열의 초기값 (순열의 가장 작은값) |
|
1 |
2 |
3(i) |
4 |
i 찾기 : 4와 3을 비교. 4보다 3이 작기 때문에 i값은 3의 index가 된다. |
|
1 |
2 |
3 |
4(j) |
j 찾기 : i가 가리키는 3보다 배열의 끝 값인 4가 더 크기 때문에 j의 값은 4의 index이다. |
|
1 |
2 |
4 |
3 |
i와 j가 가리키는 원소의 위치를 바꿔준다. |
|
1 |
2 |
4 |
3 |
i+1부터 배열의 끝까지 오름차순으로 정렬 ⇨ 다음순열 |
|
1 |
2(i) |
4 |
3 |
i 찾기 : 3과 4를 비교. 3보다 4가 크기 때문에 2와 4를 비교. 4보다 2가 작기 때문에 i값은 2의 index가 된다. |
|
1 |
2 |
4 |
3(j) |
j 찾기 : i가 가리키는 2와 배열의 끝 값인 3을 비교하면 i가 가리키는 2보다 배열의 끝 값인 3이 더 크기 때문에 j 값은 3의 index이다. |
|
1 |
3 |
4 |
2 |
i와 j가 가리키는 원소의 위치를 바꿔준다. |
|
1 |
3 |
2 |
4 |
i+1부터 배열의 끝까지 오름차순으로 정렬 ⇨ 다음순열 |
위 예제를 보면 아이템 1, 2, 3, 4로 만들 수 있는 가장 작은 수부터 바로 다음 큰 수로 증가하면서 순열을 만든다. 이것이 TNHP로 순열을 생성하는 방법이다.
■ 모든 순열을 구해주는 클래스
using System.Collections.Generic;
class TPermu
{
private int num;
private int[] arr;
public TPermu(int num)
{
this.num = num;
arr = null;
}
public int[] next()
{ // 다음 순열 못찾으면 null 리턴
//---------------------------------------------
// 첫번째 순열
//---------------------------------------------
if (arr == null)
{
arr = new int[num];
for (int k = 0; k < num; k++) arr[k] = k;
return arr;
}
//---------------------------------------------
// Find i
//---------------------------------------------
int i, j;
bool found;
found = false;
for (i = num - 1 - 1; i >= 0; i--)
{
if (arr[i] < arr[i + 1])
{
found = true;
break;
}
}
if (found == false)
return null;
//---------------------------------------------
// Find j
//---------------------------------------------
found = false;
for (j = num - 1; j >= 1; j--)
{
if (arr[j] > arr[i])
{
found = true;
break;
}
}
if (found == false)
return null;
//---------------------------------------------
// swap i, j
//---------------------------------------------
swap(ref arr[i], ref arr[j]);
//---------------------------------------------
// sorting from i+1
//---------------------------------------------
int m, n, imin;
for (m = i + 1; m < num - 1; m++)
{
imin = m;
for (n = m + 1; n < num; n++)
{
if (arr[n] < arr[imin]) imin = n;
}
swap(ref arr[m], ref arr[imin]);
}
return arr;
}
//========================================================
// swap
//========================================================
private static void swap(ref int a, ref int b)
{
int tmp = a;
a = b;
b = tmp;
}
}
int cnt = 0;
TPermu perm = new TPermu(n);
while (true)
{
int[] c = permu.next();
if (c == null) break;
for (int i = 0; i < c.Length; i++)
{
// c[i]가 구해진 순열
}
}
CombiPermu.zip
