Microsoft MVP성태의 닷넷 이야기
.NET Framework: 589. C# - 모든 경우의 수를 조합하는 코드 (1) [링크 복사], [링크+제목 복사],
조회: 21234
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 3개 있습니다.)

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

조합에 대해서는 지난번에 코드로 소개했습니다.

C# - 조합(Combination) 예제 코드
; https://www.sysnet.pe.kr/2/0/10954

그런데, 아쉽게도 코드가 그다지 쉽지 않습니다. 만약 off-line 코딩 시험을 봐야 한다면 저런 식으로 만드는데 시간이 좀 걸릴 텐데요. 개념상 좀 더 간단하게 만드는 방법이 알려져 있습니다.

예를 들어, 3개의 요소에 대한 모든 조합을 보면,

1 2 3
1 2
1 3
2 3
1
2
3
(null)

저렇게 됩니다. 아직 감이 안 오는 분들이 계실 텐데요. ^^ 숫자에 해당하는 것을 2n에 해당하는 비트 열로 바꿔보면 좀 더 명확해집니다.

23 22 21
-------
1  1  1
   1  1 
1     1
1  1
      1
   1
1
(null)

여전히 감이 안 오는 분들은, 2의 n승에 따라 우측에 그 값을 표시해 보면 됩니다.

23 22 21
4  2  1
-------
1  1  1    == 7
   1  1    == 3
1     1    == 5
1  1       == 6
      1    == 1
   1       == 2
1          == 4
(null)

우측의 값들을 나열해 정렬해 보면 "1,2,3,4,5,6,7"이 됩니다. 그럼, 정리가 되었죠? ^^ 숫자에 따른 비트는 절대 겹칠 수가 없습니다. 따라서 숫자 값을 바꾸는 것만으로 그것의 모든 조합이 자연스럽게 구성되는 것입니다.

따라서, 모든 조합의 배열 인덱스를 뽑아주는 클래스를 다음과 같이 만들 수 있습니다.

public class Combination
{
    readonly int _count;
    readonly int _numberOfAll;

    readonly int[] _sourceList;
    readonly int[] _emptyIndex;
    int[] _caseIndex;

    int _effectiveCount;

    public Combination(int [] elems)
    {
        _sourceList = elems;
        _count = _sourceList.Length;
        _numberOfAll = (1 << _count);

        _emptyIndex = new int[_count];
        for (int i = 0; i < _count; i ++)
        {
            _emptyIndex[i] = -1;
        }

        _caseIndex = new int[_count];
    }

    public IEnumerable<int []> Successor()
    {
        for (int i = 0; i < _numberOfAll; i ++)
        {
            _effectiveCount = 0;
            Array.Copy(_emptyIndex, _caseIndex, _count);

            for (int c = 0; c < _count; c++)
            {
                int mask = (1 << c); // 이 코드의 간단한 핵심.
                if ((i & mask) == mask)
                {
                    _caseIndex[_effectiveCount] = c;
                    _effectiveCount++;
                }
            }

            yield return _caseIndex;
        }
    }

    public int [] Apply()
    {
        int[] combinations = new int[_effectiveCount];

        for (int i = 0; i < _effectiveCount; i ++)
        {
            combinations[i] = _sourceList[_caseIndex[i]];
        }

        return combinations;
    }
}

사용 방법은 이렇습니다.

class Program
{
    static void Main(string[] args)
    {
        int[] list = new int[] { 200, 300, 500, 600 };
        Combination c = new Combination(list);

        foreach (var elems in c.Successor())
        {
            int [] items = c.Apply();
            PrintElems(items);
        }
    }

    private static void PrintElems(int[] elems)
    {
        Console.Write("{ ");

        foreach (var elem in elems)
        {
            Console.Write(elem + ", ");
        }

        Console.WriteLine(" }");
    }
}

출력 결과는 예상했던 대로!

{  }
{ 200,  }
{ 300,  }
{ 200, 300,  }
{ 500,  }
{ 200, 500,  }
{ 300, 500,  }
{ 200, 300, 500,  }
{ 600,  }
{ 200, 600,  }
{ 300, 600,  }
{ 200, 300, 600,  }
{ 500, 600,  }
{ 200, 500, 600,  }
{ 300, 500, 600,  }
{ 200, 300, 500, 600,  }

여기에 제네릭과 IEnumerable을 곁들이면,

using System.Collections.Generic;
using System;
using System.Collections;

public class Combination<TData> : IEnumerable<TData[]>
{
    readonly int _count;
    readonly int _numberOfAll;

    readonly TData[] _sourceList;
    readonly int[] _emptyIndex;
    int[] _caseIndex;

    int _effectiveCount;

    public Combination(TData[] elems)
    {
        _sourceList = elems;
        _count = _sourceList.Length;
        _numberOfAll = (1 << _count);

        _emptyIndex = new int[_count];
        for (int i = 0; i < _count; i++)
        {
            _emptyIndex[i] = -1;
        }

        _caseIndex = new int[_count];
    }

    public IEnumerable<int[]> Successor()
    {
        for (int i = 0; i < _numberOfAll; i++)
        {
            _effectiveCount = 0;
            Array.Copy(_emptyIndex, _caseIndex, _count);

            for (int c = 0; c < _count; c++)
            {
                int mask = (1 << c); // 이 코드의 간단한 핵심.
                if ((i & mask) == mask)
                {
                    _caseIndex[_effectiveCount] = c;
                    _effectiveCount++;
                }
            }

            yield return _caseIndex;
        }
    }

    public TData[] Apply()
    {
        TData[] combinations = new TData[_effectiveCount];

        for (int i = 0; i < _effectiveCount; i++)
        {
            combinations[i] = _sourceList[_caseIndex[i]];
        }

        return combinations;
    }

    public IEnumerator<TData[]> GetEnumerator()
    {
        return Enumerate();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return Enumerate();
    }

    IEnumerator<TData[]> Enumerate()
    {
        Combination<TData> c = new Combination<TData>(this._sourceList);

        foreach (var elems in c.Successor())
        {
            TData[] items = c.Apply();
            yield return items;
        }
    }
}

다음과 같이 사용할 수 있습니다.

{
    int[] list = new int[] { 2, 3, 5, 6 };
    Combination<int> c = new Combination<int>(list);

    foreach (var elems in c)
    {
        PrintElems(elems);
    }
}

{
    string[] list = new string[] { "2", "3", "5", "6" };
    Combination<string> c = new Combination<string>(list);

    foreach (var elems in c)
    {
        PrintElems(elems);
    }
}

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

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




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

[연관 글]






[최초 등록일: ]
[최종 수정일: 11/18/2022]

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

비밀번호

댓글 작성자
 




... 31  32  33  34  35  36  37  38  39  40  41  [42]  43  44  45  ...
NoWriterDateCnt.TitleFile(s)
12594정성태4/11/20218482.NET Framework: 1035. C# - kubectl 명령어 또는 REST API 대신 Kubernetes 클라이언트 라이브러리를 통해 프로그래밍으로 접근 [1]파일 다운로드1
12593정성태4/10/20219677개발 환경 구성: 567. Docker Desktop for Windows - kubectl proxy 없이 k8s 대시보드 접근 방법
12592정성태4/10/20219519개발 환경 구성: 566. Docker Desktop for Windows - k8s dashboard의 Kubeconfig 로그인 및 Skip 방법
12591정성태4/9/202112795.NET Framework: 1034. C# - byte 배열을 Hex(16진수) 문자열로 고속 변환하는 방법 [2]파일 다운로드1
12590정성태4/9/20219287.NET Framework: 1033. C# - .NET 4.0 이하에서 Console.IsInputRedirected 구현 [1]
12589정성태4/8/202110634.NET Framework: 1032. C# - Environment.OSVersion의 문제점 및 윈도우 운영체제의 버전을 구하는 다양한 방법 [1]
12588정성태4/7/202111166개발 환경 구성: 565. PowerShell - New-SelfSignedCertificate를 사용해 CA 인증서 생성 및 인증서 서명 방법
12587정성태4/6/202112003개발 환경 구성: 564. Windows 10 - ClickOnce 배포처럼 사용할 수 있는 MSIX 설치 파일 [1]
12586정성태4/5/20219695오류 유형: 710. Windows - Restart-Computer / shutdown 명령어 수행 시 Access is denied(E_ACCESSDENIED)
12585정성태4/5/20219406개발 환경 구성: 563. 기본 생성된 kubeconfig 파일의 내용을 새롭게 생성한 인증서로 구성하는 방법
12584정성태4/1/202110122개발 환경 구성: 562. kubeconfig 파일 없이 kubectl 옵션만으로 실행하는 방법
12583정성태3/29/202111596개발 환경 구성: 561. kubectl 수행 시 다른 k8s 클러스터로 접속하는 방법
12582정성태3/29/202110303오류 유형: 709. Visual C++ - 컴파일 에러 error C2059: syntax error: '__stdcall'
12581정성태3/28/202110218.NET Framework: 1031. WinForm/WPF에서 Console 창을 띄워 출력하는 방법 (2) - Output 디버깅 출력을 AllocConsole로 우회 [2]
12580정성태3/28/20218920오류 유형: 708. SQL Server Management Studio - Execution Timeout Expired.
12579정성태3/28/20219032오류 유형: 707. 중첩 가상화(Nested Virtualization) - The virtual machine could not be started because this platform does not support nested virtualization.
12578정성태3/27/20219300개발 환경 구성: 560. Docker Desktop for Windows 기반의 Kubernetes 구성 (2) - WSL 2 인스턴스에 kind가 구성한 k8s 서비스 위치
12577정성태3/26/202111335개발 환경 구성: 559. Docker Desktop for Windows 기반의 Kubernetes 구성 - WSL 2 인스턴스에 kind 도구로 k8s 클러스터 구성
12576정성태3/25/20219145개발 환경 구성: 558. Docker Desktop for Windows에서 DockerDesktopVM 기반의 Kubernetes 구성 (2) - k8s 서비스 위치
12575정성태3/24/20218174개발 환경 구성: 557. Docker Desktop for Windows에서 DockerDesktopVM 기반의 Kubernetes 구성
12574정성태3/23/202112266.NET Framework: 1030. C# Socket의 Close/Shutdown 동작 (동기 모드)
12573정성태3/22/202110061개발 환경 구성: 556. WSL 인스턴스 초기 설정 명령어 [1]
12572정성태3/22/20219600.NET Framework: 1029. C# - GC 호출로 인한 메모리 압축(Compaction)을 확인하는 방법파일 다운로드1
12571정성태3/21/20218757오류 유형: 706. WSL 2 기반으로 "Enable Kubernetes" 활성화 시 초기화 실패 [1]
12570정성태3/19/202113050개발 환경 구성: 555. openssl - CA로부터 인증받은 새로운 인증서를 생성하는 방법
12569정성태3/18/202112014개발 환경 구성: 554. WSL 인스턴스 export/import 방법 및 단축 아이콘 설정 방법
... 31  32  33  34  35  36  37  38  39  40  41  [42]  43  44  45  ...