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,  }

(첨부한 파일은 이 글의 코드를 포함합니다.)

---

[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[최초 등록일: 5/23/2016]
[최종 수정일: 5/5/2022]


이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

by SeongTae Jeong, mailto:techsharer at outlook.com