C# - 모든 경우의 수를 조합하는 코드 (2)
지난번 글에서 모든 경우의 수를 조합하는 코드를 알아봤는데요.
C# - 모든 경우의 수를 조합하는 코드 (1)
; https://www.sysnet.pe.kr/2/0/10977
글을 보시면 아시겠지만, "모든 경우의 수"는 2
n과 같습니다. 2의 n승이니, 이는 포화 2진 트리 형식으로도 표현이 가능합니다. 가령 2개의 요소를 갖는 경우의 수를 보면 다음과 같이 트리로 표현됩니다.
루트에서부터 하위 리프 노드로 가면서 (또는, 거꾸로) 이어지는 숫자의 배열을 나열해 보면 경우의 수와 동일한 구성을 볼 수 있습니다.
0 [0 0]
0 [0 1]
0 [1 0]
0 [1 1]
따라서, 경우의 수를 탐색하는데 재귀호출로 이렇게 표현하는 것도 가능합니다. (트리 구성은 임의 구현이 가능한데, 아래의 코드는 그 하나의 사례라고 보시면 됩니다.)
public class Node
{
public readonly Node Parent;
public readonly int Index;
public Node(Node parent, int index)
{
this.Parent = parent;
this.Index = index;
}
}
public class Combination
{
readonly int _depth;
readonly int[] _sourceList;
List<Node> _leafNodes = new List<Node>();
public Combination(int [] elems)
{
_sourceList = elems;
_depth = _sourceList.Length;
Prepare();
}
void Prepare()
{
VisitElement(1, new Node(null, 1));
VisitElement(1, new Node(null, 0));
}
private void VisitElement(int depth, Node node)
{
if (depth == _depth)
{
_leafNodes.Add(node);
return;
}
VisitElement(depth + 1, new Node(node, 1));
VisitElement(depth + 1, new Node(node, 0));
}
internal IEnumerable<int []> Combinations()
{
foreach (Node leaf in _leafNodes)
{
Node node = leaf;
List<int> elems = new List<int>();
int index = 0;
while (node != null)
{
if (node.Index == 1)
{
elems.Add(_sourceList[index]);
}
index++;
node = node.Parent;
}
yield return elems.ToArray();
}
}
}
사용은 이렇게 할 수 있고,
static void Main(string[] args)
{
int[] list = new int[] { 200, 300, 500, 600 };
Combination c = new Combination(list);
foreach (var item in c.Combinations())
{
PrintElems(item);
}
}
private static void PrintElems(int[] elems)
{
Console.Write("{ ");
foreach (var elem in elems)
{
Console.Write(elem + ", ");
}
Console.WriteLine(" }");
}
출력 결과는 모든 경우의 수입니다.
{ 200, 300, 500, 600, }
{ 300, 500, 600, }
{ 200, 500, 600, }
{ 500, 600, }
{ 200, 300, 600, }
{ 300, 600, }
{ 200, 600, }
{ 600, }
{ 200, 300, 500, }
{ 300, 500, }
{ 200, 500, }
{ 500, }
{ 200, 300, }
{ 300, }
{ 200, }
{ }
역시 개념만 알아두면, 언제든 쉽게 만들 수 있는 코드입니다.
(
첨부 파일은 이 글의 예제 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]