C# - 조합(Combination) 예제 코드 - 두 번째 이야기
조합에 대해 많이도 쓰는군요. ^^;
C# - 조합(Combination) 예제 코드
; https://www.sysnet.pe.kr/2/0/10954
C# - 모든 경우의 수를 조합하는 코드 (1)
; https://www.sysnet.pe.kr/2/0/10977
C# - 모든 경우의 수를 조합하는 코드 (2)
; https://www.sysnet.pe.kr/2/0/10978
일단 모든 경우의 수를 조합하는 코드는 더 이상 할 이야기가 없습니다. 그 정도만 알아도. ^^
단지, "
C# - 조합(Combination) 예제 코드" 글에서는 nCr의 형태로 조합하는 코드를 담고 있는데요.
이와 관련해 "해커의 기쁨"이라는 책에 보면,
해커의 기쁨 : 비트와 바이트 그리고 알고리즘 [제2판]
; http://www.yes24.com/24/goods/9218103?scode=032
18페이지에 "Gosper"가 고안했다는 알고리즘이 실려있습니다. 다음은 책의 코드를 C#의 ulong 타입으로 변경한 것입니다. (ulong이기 때문에 n <= 64 범위내에서만 코드가 정상동작합니다.)
ulong snoob(ulong x)
{
ulong smallest;
ulong ripple;
ulong ones;
smallest = x & (ulong)-(long)x;
ripple = x + smallest;
ones = x ^ ripple;
ones = (ones >> 2) / smallest;
return ripple | ones;
}
위의 함수는 입력된 x 변수의 값에 포함된 1-비트 개수를 유지하면서, 그것의 바로 다음으로 큰 수를 구해서 반환합니다. 예를 들어, 다음과 같은 역할을 하는 것입니다.
입력값: 01111 0000
출력값: 10000 0111
따라서, 나머지 처리는
C# - 모든 경우의 수를 조합하는 코드 (1) 글에서 했던 것과 유사하게 비트 값에 따른 조합 값만 추리는 작업을 추가하면 nCr 조합을 구할 수 있습니다.
public class Combination
{
readonly string[] _sourceList;
readonly ulong _startElem;
readonly ulong _endElem;
readonly int _choose;
string[] _caseIndex;
public Combination(string[] elems, int choose)
{
_choose = choose;
_sourceList = elems;
_startElem = (ulong)((1 << choose) - 1);
_endElem = _startElem << (elems.Length - choose);
_caseIndex = new string[choose];
}
public IEnumerable<string[]> Successor()
{
ulong start = _startElem;
while (true)
{
int index = 0;
for (int c = 0; c < _sourceList.Length; c++)
{
ulong mask = (ulong)1 << c;
if ((start & mask) == mask)
{
_caseIndex[index ++] = _sourceList[c];
}
}
yield return _caseIndex;
if (start == _endElem)
{
yield break;
}
start = snoob(start);
}
}
ulong snoob(ulong x)
{
ulong smallest;
ulong ripple;
ulong ones;
smallest = x & (ulong)-(long)x;
ripple = x + smallest;
ones = x ^ ripple;
ones = (ones >> 2) / smallest;
return ripple | ones;
}
}
사용은 다음과 같은 식으로 하면 되고,
class Program
{
static void Main(string[] args)
{
string[] items = new string[] { "ant", "bug", "cat", "dog", "elk" };
Combination c = new Combination(items, 3);
foreach (var elems in c.Successor())
{
PrintElems(elems);
}
}
private static void PrintElems(string[] elems)
{
Console.Write("{ ");
foreach (var elem in elems)
{
Console.Write(elem + ", ");
}
Console.WriteLine(" }");
}
}
출력값은 이렇습니다.
{ ant, bug, cat, }
{ ant, bug, dog, }
{ ant, cat, dog, }
{ bug, cat, dog, }
{ ant, bug, elk, }
{ ant, cat, elk, }
{ bug, cat, elk, }
{ ant, dog, elk, }
{ bug, dog, elk, }
{ cat, dog, elk, }
(
첨부한 파일은 이 글의 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]