Microsoft MVP성태의 닷넷 이야기
.NET Framework: 580. C# - 조합(Combination) 예제 코드 [링크 복사], [링크+제목 복사],
조회: 32330
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 4개 있습니다.)

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

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





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

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




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

[연관 글]






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

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2016-05-23 03시54분
C# - 조합(Combination) 예제 코드 - 두 번째 이야기
; http://www.sysnet.pe.kr/2/0/10979
정성태
2022-05-05 02시50분
[jhyunah21] 선생님의 글 덕분에 조합 알고리즘을 이해할 수 있었습니다. 감사합니다 선생님!
[guest]

... 151  152  153  154  155  156  157  158  159  160  161  162  [163]  164  165  ...
NoWriterDateCnt.TitleFile(s)
1012정성태4/6/201135335.NET Framework: 208. WCF - 접속된 클라이언트의 IP 주소 알아내는 방법 [1]
1011정성태3/31/201137577오류 유형: 114. 인증서 갱신 오류 - The request contains no certificate template information.
1010정성태3/30/201128363개발 환경 구성: 113. 응용 프로그램 디자인 스케치 도구 - SketchFlow [4]
1009정성태3/29/201140619개발 환경 구성: 112. Visual Studio 2010 - .NET Framework 소스 코드 디버깅 [4]
1008정성태3/27/201132884.NET Framework: 207. C# - Right operand가 음수인 Shift 연산 결과 [2]
1007정성태3/16/201133852개발 환경 구성: 111. Excel - XML 파일 연동 [5]파일 다운로드1
1006정성태3/15/201127531.NET Framework: 206. XML/XSD - 외래키처럼 참조 제한 거는 방법파일 다운로드1
1005정성태3/11/201137405개발 환경 구성: 110. 엑셀 매크로 함수 관련 오류 [2]
1004정성태3/3/201126634개발 환경 구성: 109. SharePoint Health Analyzer 디스크 부족 경고 제어
1003정성태3/3/201127637오류 유형: 113. SQL Server - DB Attach 시 Parameter name: nColIndex 오류 발생
1002정성태3/2/201125977Team Foundation Server: 44. TFS 설치 후, Team Portal의 Dashboard를 빠르게 확인하는 방법
1001정성태3/2/201130067Team Foundation Server: 43. TFS 2010 + SharePoint 2010 설치
1000정성태3/1/201135130오류 유형: 112. Remote FX RDP 연결 시 오류 유형 2가지 [5]
999정성태2/28/201148409개발 환경 구성: 108. RemoteFX - Windows 7 가상 머신에서 DirectX 9c 환경을 제공 [5]
998정성태2/27/201122272Team Foundation Server: 42. TFS Application-Tier만 재설치
996정성태2/12/201139708디버깅 기술: 35. windbg - 분석 예: 시작하자마자 비정상 종료하는 프로세스 - NullReferenceException
995정성태2/11/201158143.NET Framework: 205. 코드(C#)를 통한 풀 덤프 만드는 방법 [4]
994정성태2/10/201138105디버깅 기술: 34. Windbg - ERROR: Unable to load DLL mscordacwks_x86_x86_2.0.50727.4200.dll, Win32 error 0n2 [1]
993정성태2/10/201130387개발 환경 구성: 107. 하나의 WPF 프로젝트를 WinExe / Library로 빌드하는 방법
992정성태10/15/201131279개발 환경 구성: 106. VSS(Volume Shadow Service)를 이용한 Hyper-V VM 백업/복원 [2]
991정성태2/6/201150774개발 환경 구성: 105. 풀 덤프 파일을 남기는 방법 [4]
990정성태2/2/201135852개발 환경 구성: 104. Visual C++ Custom Build Tool 사용예 [1]파일 다운로드1
989정성태2/1/201132231개발 환경 구성: 103. DOS batch - 동기 방식으로 원격 서비스 제어
988정성태1/30/201128155개발 환경 구성: 102. MSBuild - DefineConstants에 다중 전처리 값 설정
987정성태1/29/201141477디버깅 기술: 33. PDB Symbol 로드 오류 - Cannot find or open the PDB file. [2]
986정성태1/26/201132976.NET Framework: 204. 분리된 ThreadPool 사용 - Smart Thread Pool
... 151  152  153  154  155  156  157  158  159  160  161  162  [163]  164  165  ...