c# 멱집합 구하는 예제 – linq

Bya programming trader

​어떠한 집합의 원소들로 구성한 집합을 멱집합이라고 한다. 한자로는 羃集合이라고 쓰는데 羃은 ‘덮다’, ‘곱한다’는 뜻이다. 같은 수들을 한 번 곱하면 제곱이라 하고 세 번 이상 곱하면 거듭제곱이라 하며 거듭제곱한 수를 멱수라 한다. 영어로는 power set라 하는데 2^3에서 2를 base라 하고 3을 power라 한다.

이 집합은 왜 이렇게 어려운 이름을 갖게 되었을까? 그 개수가 2를 기본 집합의 원소 수만큼 거듭제곱한 값이기 때문이다. 예를 들어 { 1, 2, 3 }의 멱집합은 { }, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 }으로 2^3개 나온다. 아무것도 없는 { }가 포함되는 것에 유의한다.

c#으로는 linq를 이용하여 한 줄로 구현할 수 있다.

private void Form1_Load(object sender, EventArgs e)
{
    List<int> _Ints = new() { 1, 2, 3, 4, 5 };

    IEnumerable<IEnumerable<int>> _Ints_s =  GetPowerSet(_Ints);

    int _Count = default;

    foreach (var item1 in _Ints_s)
    {
        _Count++;

        textBox1.AppendText(_Count.ToString() + " ");

        foreach (var item2 in item1)
        {
            textBox1.AppendText(item2.ToString() + " ");
        }

        textBox1.AppendText("\r\n");
    }
}

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> _List)
{
    return from m in Enumerable.Range(0, 1 << _List.Count) select from i in Enumerable.Range(0, _List.Count) where (m & (1 << i)) != 0 select _List[i];
}
Post Views: 2
Post Tags: