Microsoft MVP성태의 닷넷 이야기
.NET Framework: 591. C# - 조합(Combination) 예제 코드 - 두 번째 이야기 [링크 복사], [링크+제목 복사],
조회: 28128
글쓴 사람
정성태 (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)
11213정성태5/26/201726918오류 유형: 393. TFS - The underlying connection was closed: Could not establish trust relationship for the SSL/TLS secure channel.
11212정성태5/26/201726114오류 유형: 392. Windows Server 2016에 KB4019472 업데이트가 실패하는 경우
11211정성태5/26/201724530오류 유형: 391. BeginInvoke에 전달한 람다 함수에 CS1660 에러가 발생하는 경우
11210정성태5/25/201724827기타: 65. ActiveX 없는 전자 메일에 사용된 "개인정보 보호를 위해 암호화된 보안메일"의 암호화 방법
11209정성태5/25/201773678Windows: 143. Windows 10의 Recovery 파티션을 삭제 및 새로 생성하는 방법 [16]
11208정성태5/25/201730693오류 유형: 390. diskpart의 set id 명령어에서 "The specified type is not in the correct format." 오류 발생
11207정성태5/24/201732539Windows: 142. Windows 10의 복구 콘솔로 부팅하는 방법
11206정성태5/24/201725531오류 유형: 389. DISM.exe - The specified image in the specified wim is already mounted for read/write access.
11205정성태5/24/201724968.NET Framework: 658. C#의 tail call 구현은? [1]
11204정성태5/22/201734547개발 환경 구성: 316. 간단하게 살펴보는 Docker for Windows [7]
11203정성태5/19/201721473오류 유형: 388. docker - Host does not exist: "default"
11202정성태5/19/201722781오류 유형: 387. WPF - There is no registered CultureInfo with the IetfLanguageTag 'ug'.
11201정성태5/16/201727052오류 유형: 386. WPF - .NET 3.5 이하에서 TextBox에 한글 입력 시 TextChanged 이벤트의 비정상 종료 문제 [1]파일 다운로드1
11200정성태5/16/201723702오류 유형: 385. WPF - 폰트가 없어 System.IO.FileNotFoundException 예외가 발생하는 경우
11199정성태5/16/201723962.NET Framework: 657. CultureInfo.GetCultures가 반환하는 값
11198정성태5/10/201727010.NET Framework: 656. Windows Forms의 오류(Exception) 처리 방법에 대한 차이점 설명
11197정성태5/8/201722184개발 환경 구성: 315. VHD 파일의 최소 크기파일 다운로드1
11196정성태5/4/201723918오류 유형: 384. Msvm_ImageManagementService WMI 객체를 사용할 때 오류 상황 정리 [1]
11195정성태5/3/201725233.NET Framework: 655. .NET Framework 4.7 릴리스
11194정성태5/3/201726090오류 유형: 383. net use 명령어로 네트워크 드라이브 연결 시 "System error 67 has occurred." 오류 발생
11193정성태5/3/201723700Windows: 141. 설치된 Windows로부터 설치 이미지를 만드는 방법
11192정성태5/2/201725982Windows: 140. unattended.xml/autounattend.xml 파일을 마련하는 방법
11191정성태5/2/201726894Windows: 139. Dell Venue 8 Pro 태블릿에 USB를 이용한 윈도우 운영체제 설치 방법
11190정성태5/2/201732417Windows: 138. Windows 운영체제의 ISO 설치 파일에 미리 Device driver를 준비하는 방법
11189정성태5/2/201723083Windows: 137. Windows 7 USB/DVD DOWNLOAD TOOL로 98%에서 실패하는 경우
11188정성태4/27/201726443VC++: 118. Win32 HANDLE 자료형의 이모저모 [2]
... 106  107  108  109  110  111  [112]  113  114  115  116  117  118  119  120  ...