Microsoft MVP성태의 닷넷 이야기
.NET Framework: 591. C# - 조합(Combination) 예제 코드 - 두 번째 이야기 [링크 복사], [링크+제목 복사],
조회: 24557
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 1개 있습니다.)

C# - 조합(Combination) 예제 코드 - 두 번째 이야기

조합에 대해 많이도 쓰는군요. ^^;

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

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

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

일단 모든 경우의 수를 조합하는 코드는 더 이상 할 이야기가 없습니다. 그 정도만 알아도. ^^

단지, "C# - 조합(Combination) 예제 코드" 글에서는 nCr의 형태로 조합하는 코드를 담고 있는데요.

이와 관련해 "해커의 기쁨"이라는 책에 보면,

해커의 기쁨  : 비트와 바이트 그리고 알고리즘 [제2판]
; http://www.yes24.com/24/goods/9218103?scode=032

18페이지에 "Gosper"가 고안했다는 알고리즘이 실려있습니다. 다음은 책의 코드를 C#의 ulong 타입으로 변경한 것입니다. (ulong이기 때문에 n <= 64 범위내에서만 코드가 정상동작합니다.)

ulong snoob(ulong x)
{
    ulong smallest;
    ulong ripple;
    ulong ones;

    smallest = x & (ulong)-(long)x;
    ripple = x + smallest;
    ones = x ^ ripple;
    ones = (ones >> 2) / smallest;

    return ripple | ones;
}

위의 함수는 입력된 x 변수의 값에 포함된 1-비트 개수를 유지하면서, 그것의 바로 다음으로 큰 수를 구해서 반환합니다. 예를 들어, 다음과 같은 역할을 하는 것입니다.

입력값: 01111 0000
출력값: 10000 0111

따라서, 나머지 처리는 C# - 모든 경우의 수를 조합하는 코드 (1) 글에서 했던 것과 유사하게 비트 값에 따른 조합 값만 추리는 작업을 추가하면 nCr 조합을 구할 수 있습니다.

public class Combination
{
    readonly string[] _sourceList;
    readonly ulong _startElem;
    readonly ulong _endElem;
    readonly int _choose;

    string[] _caseIndex;

    public Combination(string[] elems, int choose)
    {
        _choose = choose;
        _sourceList = elems;

        _startElem = (ulong)((1 << choose) - 1);
        _endElem = _startElem << (elems.Length - choose);

        _caseIndex = new string[choose];
    }

    public IEnumerable<string[]> Successor()
    {
        ulong start = _startElem;

        while (true)
        {
            int index = 0;

            for (int c = 0; c < _sourceList.Length; c++)
            {
                ulong mask = (ulong)1 << c;
                if ((start & mask) == mask)
                {
                    _caseIndex[index ++] = _sourceList[c];
                }
            }

            yield return _caseIndex;

            if (start == _endElem)
            {
                yield break;
            }

            start = snoob(start);
        }
    }

    ulong snoob(ulong x)
    {
        ulong smallest;
        ulong ripple;
        ulong ones;

        smallest = x & (ulong)-(long)x;
        ripple = x + smallest;
        ones = x ^ ripple;
        ones = (ones >> 2) / smallest;

        return ripple | ones;
    }
}

사용은 다음과 같은 식으로 하면 되고,

class Program
{
    static void Main(string[] args)
    {
        string[] items = new string[] { "ant", "bug", "cat", "dog", "elk" };

        Combination c = new Combination(items, 3);

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

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

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

        Console.WriteLine(" }");
    }
}

출력값은 이렇습니다.

{ ant, bug, cat,  }
{ ant, bug, dog,  }
{ ant, cat, dog,  }
{ bug, cat, dog,  }
{ ant, bug, elk,  }
{ ant, cat, elk,  }
{ bug, cat, elk,  }
{ ant, dog, elk,  }
{ bug, dog, elk,  }
{ cat, dog, elk,  }

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




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

[연관 글]






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

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

비밀번호

댓글 작성자
 




... [106]  107  108  109  110  111  112  113  114  115  116  117  118  119  120  ...
NoWriterDateCnt.TitleFile(s)
11260정성태8/3/201718255.NET Framework: 670. C# - 실행 파일로부터 공개키를 추출하는 방법
11259정성태8/2/201717925.NET Framework: 669. 지연 서명된 어셈블리를 sn.exe -Vr 등록 없이 사용하는 방법
11258정성태8/1/201718327.NET Framework: 668. 지연 서명된 DLL과 서명된 DLL의 차이점파일 다운로드1
11257정성태7/31/201718973.NET Framework: 667. bypassTrustedAppStrongNames 옵션 설명파일 다운로드1
11256정성태7/25/201720041디버깅 기술: 90. windbg의 lm 명령으로 보이지 않는 .NET 4.0 ClassLibrary를 명시적으로 로드하는 방법 [1]
11255정성태7/18/201722684디버깅 기술: 89. Win32 Debug CRT Heap Internals의 0xBAADF00D 표시 재현 [1]파일 다운로드3
11254정성태7/17/201719019개발 환경 구성: 322. "Visual Studio Emulator for Android" 에뮬레이터를 "Android Studio"와 함께 쓰는 방법
11253정성태7/17/201719084Math: 21. "Coding the Matrix" 문제 2.5.1 풀이 [1]파일 다운로드1
11252정성태7/13/201718299오류 유형: 411. RTVS 또는 PTVS 실행 시 Could not load type 'Microsoft.VisualStudio.InteractiveWindow.Shell.IVsInteractiveWindowFactory2'
11251정성태7/13/201716360디버깅 기술: 88. windbg 분석 - webengine4.dll의 MgdExplicitFlush에서 발생한 System.AccessViolationException의 crash 문제 (2)
11250정성태7/13/201720009디버깅 기술: 87. windbg 분석 - webengine4.dll의 MgdExplicitFlush에서 발생한 System.AccessViolationException의 crash 문제 [1]
11249정성태7/12/201717833오류 유형: 410. LoadLibrary("[...].dll") failed - The specified procedure could not be found.
11248정성태7/12/201724246오류 유형: 409. pip install pefile - 'cp949' codec can't decode byte 0xe2 in position 208687: illegal multibyte sequence
11247정성태7/12/201718623오류 유형: 408. SqlConnection 객체 생성 시 무한 대기 문제파일 다운로드1
11246정성태7/11/201717848VS.NET IDE: 118. Visual Studio - 다중 폴더에 포함된 파일들에 대한 "Copy to Output Directory"를 한 번에 설정하는 방법
11245정성태7/10/201723293개발 환경 구성: 321. Visual Studio Emulator for Android 소개 [2]
11244정성태7/10/201722435오류 유형: 407. Visual Studio에서 ASP.NET Core 실행할 때 dotnet.exe 프로세스의 -532462766 오류 발생 [1]
11243정성태7/10/201719112.NET Framework: 666. dotnet.exe - 윈도우 운영체제에서의 .NET Core 버전 찾기 규칙
11242정성태7/8/201719765제니퍼 .NET: 27. 제니퍼 닷넷 적용 사례 (7) - 노후된 스토리지 장비로 인한 웹 서비스 Hang (멈춤) 현상
11241정성태7/8/201718587오류 유형: 406. Xamarin 빌드 에러 XA5209, APT0000
11240정성태7/7/201721042.NET Framework: 665. ClickOnce를 웹 브라우저를 이용하지 않고 쿼리 문자열을 전달하면서 실행하는 방법 [3]파일 다운로드1
11239정성태7/6/201723121.NET Framework: 664. Protocol Handler - 웹 브라우저에서 데스크톱 응용 프로그램을 실행하는 방법 [5]파일 다운로드1
11238정성태7/6/201720519오류 유형: 405. NT 서비스 시작 시 "Error 1067: The process terminated unexpectedly." 오류 발생 [2]
11237정성태7/5/201722114.NET Framework: 663. C# - PDB 파일 경로를 PE 파일로부터 얻는 방법파일 다운로드1
11236정성태7/4/201724976.NET Framework: 662. C# - VHD/VHDX 가상 디스크를 마운트하지 않고 파일을 복사하는 방법파일 다운로드1
11235정성태6/29/201719242Math: 20. Matlab/Octave로 Gram-Schmidt 정규 직교 집합 구하는 방법
... [106]  107  108  109  110  111  112  113  114  115  116  117  118  119  120  ...