Microsoft MVP성태의 닷넷 이야기
.NET Framework: 591. C# - 조합(Combination) 예제 코드 - 두 번째 이야기 [링크 복사], [링크+제목 복사],
조회: 28286
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




... 151  152  153  154  155  156  157  158  159  [160]  161  162  163  164  165  ...
NoWriterDateCnt.TitleFile(s)
1142정성태10/8/201139292.NET Framework: 244. 윈도우 폼을 열고 닫는 것만으로 메모리 leak이 발생할까? [2]파일 다운로드1
1141정성태10/7/201137635.NET Framework: 243. DataTable에 대해서 Dispose 메서드를 호출할 필요가 있을까? [4]파일 다운로드1
1140정성태10/6/201131154.NET Framework: 242. 닷넷 개발자 입장에서 이해해 보는 자바의 서블릿, JSP
1138정성태10/1/201150268Java: 11. 웹 로직에서 MS-SQL 서버 연결 [2]
1137정성태9/30/201133943Java: 10. 닷넷 개발자가 설치해 본 Oracle WebLogic Server - 설치 및 기본 도메인 구성
1136정성태9/29/201129736개발 환경 구성: 131. Visual Studio - ASP.NET의 Code-behind처럼 cs 파일을 그룹핑하는 매크로 함수 [2]파일 다운로드1
1135정성태9/29/201126720오류 유형: 138. TF10216: Team Foundation services are currently unavailable
1134정성태9/27/201134285.NET Framework: 241. C# 5.0에 새로 추가된 Caller Info 특성 [5]
1133정성태9/25/201138054VC++: 54. C++로 만든 WinRT 프로그램 [2]
1132정성태9/24/201177690Java: 9. 자바의 keytool.exe 사용법과 Tomcat의 SSL 통신 설정
1131정성태9/23/201133487Java: 8. 닷넷 개발자가 구현해 본 자바 웹 서비스 (2)
1130정성태9/23/201141871Java: 7. 닷넷 개발자가 구현해 본 자바 웹 서비스 (1)파일 다운로드2
1129정성태9/22/201133443개발 환경 구성: 130. Hyper-V에 MS-DOS VM 만드는 방법 - MSDN 구독자 대상 [3]
1128정성태9/20/201133706오류 유형: 137. KB2449742 보안 업데이트로 인한 충돌 문제 해결 - 두 번째 이야기
1127정성태9/19/201137134Java: 6. Java에서 MySQL 사용 [2]
1126정성태9/18/201132328Math: 3. "유클리드 호제법"과 "Bezout's identity" 구현 코드(C#)파일 다운로드1
1125정성태9/17/201130125Windows: 54. Windows 8 개발자 Preview를 사용해 보고... [2]
1124정성태9/17/201130316.NET Framework: 240. System.Collections.ArrayList가 .NET 4.5에서 지원이 안된다??? [2]
1123정성태9/17/201169809Windows: 53. 2가지 모드의 Internet Explorer 10과 ActiveX [6]
1122정성태9/16/201137062Windows: 52. 새롭게 지원되는 WinRT 응용 프로그램 [7]
1121정성태9/12/201132340Java: 5. WTP 내에서 서블릿을 실행하는 환경
1120정성태9/11/201132098.NET Framework: 239. IHttpHandler.IsReusable 속성 이야기파일 다운로드1
1119정성태9/11/201130454Java: 4. 이클립스에 WTP SDK가 설치되지 않는다면? [2]
1118정성태9/11/201143100Java: 3. 이클립스에서 서블릿 디버깅하는 방법 [4]
1117정성태9/9/201129964제니퍼 .NET: 17. 제니퍼 닷넷 적용 사례 (2) - 웹 애플리케이션 hang의 원인을 알려주다.
1116정성태9/8/201161156Java: 2. 자바에서 "Microsoft SQL Server JDBC Driver" 사용하는 방법
... 151  152  153  154  155  156  157  158  159  [160]  161  162  163  164  165  ...