C# - 모든 경우의 수를 조합하는 코드 (1)
조합에 대해서는 지난번에 코드로 소개했습니다.
C# - 조합(Combination) 예제 코드
; https://www.sysnet.pe.kr/2/0/10954
그런데, 아쉽게도 코드가 그다지 쉽지 않습니다. 만약 off-line 코딩 시험을 봐야 한다면 저런 식으로 만드는데 시간이 좀 걸릴 텐데요. 개념상 좀 더 간단하게 만드는 방법이 알려져 있습니다.
예를 들어, 3개의 요소에 대한 모든 조합을 보면,
1 2 3
1 2
1 3
2 3
1
2
3
(null)
저렇게 됩니다. 아직 감이 안 오는 분들이 계실 텐데요. ^^ 숫자에 해당하는 것을 2
n에 해당하는 비트 열로 바꿔보면 좀 더 명확해집니다.
23 22 21
-------
1 1 1
1 1
1 1
1 1
1
1
1
(null)
여전히 감이 안 오는 분들은, 2의 n승에 따라 우측에 그 값을 표시해 보면 됩니다.
23 22 21
4 2 1
-------
1 1 1 == 7
1 1 == 3
1 1 == 5
1 1 == 6
1 == 1
1 == 2
1 == 4
(null)
우측의 값들을 나열해 정렬해 보면 "1,2,3,4,5,6,7"이 됩니다. 그럼, 정리가 되었죠? ^^ 숫자에 따른 비트는 절대 겹칠 수가 없습니다. 따라서 숫자 값을 바꾸는 것만으로 그것의 모든 조합이 자연스럽게 구성되는 것입니다.
따라서, 모든 조합의 배열 인덱스를 뽑아주는 클래스를 다음과 같이 만들 수 있습니다.
public class Combination
{
readonly int _count;
readonly int _numberOfAll;
readonly int[] _sourceList;
readonly int[] _emptyIndex;
int[] _caseIndex;
int _effectiveCount;
public Combination(int [] elems)
{
_sourceList = elems;
_count = _sourceList.Length;
_numberOfAll = (1 << _count);
_emptyIndex = new int[_count];
for (int i = 0; i < _count; i ++)
{
_emptyIndex[i] = -1;
}
_caseIndex = new int[_count];
}
public IEnumerable<int []> Successor()
{
for (int i = 0; i < _numberOfAll; i ++)
{
_effectiveCount = 0;
Array.Copy(_emptyIndex, _caseIndex, _count);
for (int c = 0; c < _count; c++)
{
int mask = (1 << c); // 이 코드의 간단한 핵심.
if ((i & mask) == mask)
{
_caseIndex[_effectiveCount] = c;
_effectiveCount++;
}
}
yield return _caseIndex;
}
}
public int [] Apply()
{
int[] combinations = new int[_effectiveCount];
for (int i = 0; i < _effectiveCount; i ++)
{
combinations[i] = _sourceList[_caseIndex[i]];
}
return combinations;
}
}
사용 방법은 이렇습니다.
class Program
{
static void Main(string[] args)
{
int[] list = new int[] { 200, 300, 500, 600 };
Combination c = new Combination(list);
foreach (var elems in c.Successor())
{
int [] items = c.Apply();
PrintElems(items);
}
}
private static void PrintElems(int[] elems)
{
Console.Write("{ ");
foreach (var elem in elems)
{
Console.Write(elem + ", ");
}
Console.WriteLine(" }");
}
}
출력 결과는 예상했던 대로!
{ }
{ 200, }
{ 300, }
{ 200, 300, }
{ 500, }
{ 200, 500, }
{ 300, 500, }
{ 200, 300, 500, }
{ 600, }
{ 200, 600, }
{ 300, 600, }
{ 200, 300, 600, }
{ 500, 600, }
{ 200, 500, 600, }
{ 300, 500, 600, }
{ 200, 300, 500, 600, }
여기에 제네릭과 IEnumerable을 곁들이면,
using System.Collections.Generic;
using System;
using System.Collections;
public class Combination<TData> : IEnumerable<TData[]>
{
readonly int _count;
readonly int _numberOfAll;
readonly TData[] _sourceList;
readonly int[] _emptyIndex;
int[] _caseIndex;
int _effectiveCount;
public Combination(TData[] elems)
{
_sourceList = elems;
_count = _sourceList.Length;
_numberOfAll = (1 << _count);
_emptyIndex = new int[_count];
for (int i = 0; i < _count; i++)
{
_emptyIndex[i] = -1;
}
_caseIndex = new int[_count];
}
public IEnumerable<int[]> Successor()
{
for (int i = 0; i < _numberOfAll; i++)
{
_effectiveCount = 0;
Array.Copy(_emptyIndex, _caseIndex, _count);
for (int c = 0; c < _count; c++)
{
int mask = (1 << c); // 이 코드의 간단한 핵심.
if ((i & mask) == mask)
{
_caseIndex[_effectiveCount] = c;
_effectiveCount++;
}
}
yield return _caseIndex;
}
}
public TData[] Apply()
{
TData[] combinations = new TData[_effectiveCount];
for (int i = 0; i < _effectiveCount; i++)
{
combinations[i] = _sourceList[_caseIndex[i]];
}
return combinations;
}
public IEnumerator<TData[]> GetEnumerator()
{
return Enumerate();
}
IEnumerator IEnumerable.GetEnumerator()
{
return Enumerate();
}
IEnumerator<TData[]> Enumerate()
{
Combination<TData> c = new Combination<TData>(this._sourceList);
foreach (var elems in c.Successor())
{
TData[] items = c.Apply();
yield return items;
}
}
}
다음과 같이 사용할 수 있습니다.
{
int[] list = new int[] { 2, 3, 5, 6 };
Combination<int> c = new Combination<int>(list);
foreach (var elems in c)
{
PrintElems(elems);
}
}
{
string[] list = new string[] { "2", "3", "5", "6" };
Combination<string> c = new Combination<string>(list);
foreach (var elems in c)
{
PrintElems(elems);
}
}
개념만 알아두면, 언제든지 쉽게 다시 만들 수 있는 코드입니다. ^^
(
첨부 파일은 이 글의 예제 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]