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

비밀번호

댓글 작성자
 




... 31  32  33  34  35  36  37  38  39  40  41  42  [43]  44  45  ...
NoWriterDateCnt.TitleFile(s)
12957정성태2/6/202218338개발 환경 구성: 636. ffmpeg.exe를 이용해 planar 포맷의 데이터를 packed 형식으로 변환하는 방법? [2]
12956정성태2/4/202219222.NET Framework: 1148. C# - ffmpeg(FFmpeg.AutoGen) - decoding 과정 [2]파일 다운로드1
12955정성태2/4/202217472개발 환경 구성: 635. 비주얼 스튜디오에서 실행하던 ASP.NET Core (.NET Framework) 응용 프로그램을 명령행에서 실행하는 방법 (2)
12954정성태2/4/202215645VS.NET IDE: 173. 비주얼 스튜디오 - Output 창에 색상이 지정된 출력 결과가 "[39m[22m" 식의 문자로 나오는 문제
12953정성태2/2/202216603Linux: 48. Windows 11 + WSL 우분투 GUI 환경에서 한글 출력
12952정성태2/2/202218021.NET Framework: 1148. C# - ffmpeg(FFmpeg.AutoGen)를 이용한 오디오 필터 예제(filter_audio.c)파일 다운로드1
12951정성태2/2/202216460.NET Framework: 1147. C# - ffmpeg(FFmpeg.AutoGen)를 이용한 오디오 필터링 예제(filtering_audio.c)파일 다운로드1
12950정성태2/1/202218443.NET Framework: 1146. .NET 6에 추가되지 않은 Generic Math (예: INumber<T>)
12949정성태2/1/202217260.NET Framework: 1145. C# - ffmpeg(FFmpeg.AutoGen) - Codec 정보 열람 및 사용 준비파일 다운로드1
12948정성태1/30/202218301.NET Framework: 1144. C# - ffmpeg(FFmpeg.AutoGen) AVFormatContext를 이용해 ffprobe처럼 정보 출력파일 다운로드1
12947정성태1/30/202218148개발 환경 구성: 634. ffmpeg.exe - 기존 동영상 컨테이너에 다중 스트림을 추가하는 방법
12946정성태1/28/202217930오류 유형: 792. .NET Core - 로컬 개발 중에 docker 호스팅으로 바꾸는 경우 SQL 서버 접근 방법
12945정성태1/28/202218230오류 유형: 791. SQL 서버 로그인 시 localhost는 되고, 127.0.0.1로는 안 되는 문제
12944정성태1/28/202222035.NET Framework: 1143. C# - Entity Framework Core 6 개요
12943정성태1/27/202220964.NET Framework: 1142. .NET 5+로 포팅 시 플랫폼 호환성 경고 메시지(SYSLIB0006, SYSLIB0011, CA1416) [1]파일 다운로드1
12942정성태1/27/202219896.NET Framework: 1141. XmlSerializer와 Dictionary 타입파일 다운로드1
12941정성태1/26/202220458오류 유형: 790. AKS/k8s - pod 상태가 Pending으로 지속되는 경우
12940정성태1/26/202216633오류 유형: 789. AKS에서 hpa에 따른 autoscale 기능이 동작하지 않는다면?
12939정성태1/25/202219310.NET Framework: 1140. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 MP3 오디오 파일 인코딩/디코딩하는 예제 [1]파일 다운로드1
12938정성태1/24/202222107개발 환경 구성: 633. Docker Desktop + k8s 환경에서 local 이미지를 사용하는 방법
12937정성태1/24/202220389.NET Framework: 1139. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 오디오(mp2) 인코딩하는 예제(encode_audio.c) [2]파일 다운로드1
12936정성태1/22/202218323.NET Framework: 1138. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 멀티미디어 파일의 메타데이터를 보여주는 예제(metadata.c)파일 다운로드1
12935정성태1/22/202220533.NET Framework: 1137. ffmpeg의 파일 해시 예제(ffhash.c)를 C#으로 포팅파일 다운로드1
12934정성태1/22/202219745오류 유형: 788. Warning C6262 Function uses '65564' bytes of stack: exceeds /analyze:stacksize '16384'. Consider moving some data to heap. [2]
12933정성태1/21/202220364.NET Framework: 1136. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 MP2 오디오 파일 디코딩 예제(decode_audio.c)파일 다운로드1
12932정성태1/20/202221932.NET Framework: 1135. C# - ffmpeg(FFmpeg.AutoGen)로 하드웨어 가속기를 이용한 비디오 디코딩 예제(hw_decode.c) [2]파일 다운로드1
... 31  32  33  34  35  36  37  38  39  40  41  42  [43]  44  45  ...