C# - 모든 경우의 수를 조합하는 코드 (2)

지난번 글에서 모든 경우의 수를 조합하는 코드를 알아봤는데요.

C# - 모든 경우의 수를 조합하는 코드 (1)
; https://www.sysnet.pe.kr/2/0/10977

글을 보시면 아시겠지만, "모든 경우의 수"는 2ⁿ과 같습니다. 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,  }
{  }

역시 개념만 알아두면, 언제든 쉽게 만들 수 있는 코드입니다.

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

---

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

[최초 등록일: 5/23/2016]
[최종 수정일: 6/27/2021]


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

by SeongTae Jeong, mailto:techsharer at outlook.com