C# - 조합(Combination) 예제 코드

조합 코드가 간혹 쓰이는 경우가 있는데, 거의 템플릿에 가깝게 쓸 수 있어서 그냥 다음의 소스 코드를 그대로 가져다 써도 됩니다.

Generating the mth Lexicographical Element of a Mathematical Combination
; https://msdn.microsoft.com/en-us/library/aa289166(v=vs.71).aspx

Using Combinations to Improve Your Software Test Case Generation
; https://docs.microsoft.com/en-us/archive/msdn-magazine/2004/july/using-combinations-to-improve-your-software-test-case-generation

using System;
using System.Text;

namespace ConsoleApplication1
{
    class Combination
    {
        private long n = 0;
        private long k = 0;
        private long[] data = null;

        public Combination(long n, long k)
        {
            if (n < 0 || k < 0)
            {
                throw new Exception("Negative parameter in constructor");
            }

            this.n = n;
            this.k = k;
            this.data = new long[k];

            for (long i = 0; i < k; ++i)
            {
                this.data[i] = i;
            }
        }

        public Combination Successor()
        {
            if (this.data.Length == 0 ||
                this.data[0] == this.n - this.k)
            {
                return null;
            }

            Combination answer = new Combination(this.n, this.k);

            long i;
            for (i = 0; i < this.k; ++i)
            {
                answer.data[i] = this.data[i];
            }

            for (i = this.k - 1; i > 0 && answer.data[i] == this.n - this.k + i; --i) ;

            ++answer.data[i];

            for (long j = i; j < this.k - 1; ++j)
            {
                answer.data[j + 1] = answer.data[j] + 1;
            }

            return answer;
        }

        public string[] ApplyTo(string[] strarr)
        {
            if (strarr.Length != this.n)
            {
                throw new Exception("Bad array size");
            }

            string[] result = new string[this.k];

            for (long i = 0; i < result.Length; ++i)
            {
                result[i] = strarr[this.data[i]];
            }

            return result;
        }

        public static long Choose(long n, long k)
        {
            if (n < 0 || k < 0)
            {
                throw new Exception("Invalid negative parameter in Choose()");
            }

            if (n < k)
            {
                return 0;
            }

            if (n == k)
            {
                return 1;
            }

            long delta, iMax;

            if (k < n - k)
            {
                delta = n - k;
                iMax = k;
            }
            else
            {
                delta = k;
                iMax = n - k;
            }

            long answer = delta + 1;

            for (long i = 2; i <= iMax; ++i)
            {
                checked { answer = (answer * (delta + i)) / i; }
            }

            return answer;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            sb.Append("{ ");

            for (long i = 0; i < this.k; ++i)
            {
                sb.AppendFormat("{0} ", this.data[i]);
            }

            sb.Append("}");

            return sb.ToString();
        }
    }
}

위의 Combination 타입은 항목들의 순서를 직접 바꾸는 방식이 아닌, 항목들의 배열 인덱스 숫자를 바꾸는 방식으로 동작합니다. 예를 들어, 위의 코드를 5개의 항목 중에 3개를 뽑는 인덱스 조합을 다음과 같이 출력해 볼 수 있습니다.

Combination c = new Combination(5, 3);

while (c != null)
{
    Console.WriteLine(c.ToString());
    c = c.Successor();
}

출력 결과는 이렇게 나옵니다.

{ 0 1 2 }
{ 0 1 3 }
{ 0 1 4 }
{ 0 2 3 }
{ 0 2 4 }
{ 0 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 3 4 }
{ 2 3 4 }

출력된 숫자의 범위는 0 ~ 4이므로, 그냥 이것을 조합으로 보여주고 싶은 배열의 인덱스로 사용해도 됩니다.

따라서, 다음과 같은 배열이 있다고 가정할 때,

{ "ant", "bug", "cat", "dog", "elk" }

이 중에서 3개의 항목을 뽑는 모든 조합을 다음과 같이 구할 수 있습니다.

string[] items = new string[] { "ant", "bug", "cat", "dog", "elk" };
Combination c = new Combination(items.Length, 3); // 5개 중에 3개를 취하는 조합

string[] snapshot = null;

while (c != null)
{
    snapshot = c.ApplyTo(items);
    DisplayItems(snapshot); // 배열의 내용을 출력하는 메서드

    c = c.Successor();
}

출력 결과는 우리가 원하는 조합을 보여줍니다.

{ ant, bug, cat }
{ ant, bug, dog }
{ ant, bug, elk }
{ ant, cat, dog }
{ ant, cat, elk }
{ ant, dog, elk }
{ bug, cat, dog }
{ bug, cat, elk }
{ bug, dog, elk }
{ cat, dog, elk }

참고로, 단순히 총 조합의 수만 알고 싶다면 Choose 정적 메서드를 호출해 주면 됩니다.

Console.WriteLine("# of combination: " + Combination.Choose(5, 3));
// 출력 결과: 10

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

$\begin{pmatrix}n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!} = \begin{cases} \begin{pmatrix}n - 1 \\ k - 1 \end{pmatrix} + \begin{pmatrix}n - 1 \\ k \end{pmatrix} &\mbox { if } 0 < k < n \\ 1 &\mbox { if } \: k = 0 \: or \: k = n \end{cases}$

---

조합도 다양하게 응용이 가능한데요. 가령 '중복 가능한 조합'이 필요하다면 다음의 코드를 가져다 쓰시면 됩니다. ^^

방탈출3 - Room 10의 '중복가능한 조합' 문제를 위한 C# 프로그래밍
; https://www.sysnet.pe.kr/2/0/1102

---

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

[최초 등록일: 5/3/2016]
[최종 수정일: 8/31/2021]


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

by SeongTae Jeong, mailto:techsharer at outlook.com