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