성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
[정성태] 저렇게 조각 코드 말고, 실제로 재현이 되는 예제 프로젝트를 압...
[정성태] Modules 창(Ctrl+Shift+U)을 띄워서, 해당 Op...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>C# - 조합(Combination) 예제 코드 - 두 번째 이야기</h1> <p> 조합에 대해 많이도 쓰는군요. ^^;<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > C# - 조합(Combination) 예제 코드 ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/10954'>http://www.sysnet.pe.kr/2/0/10954</a> C# - 모든 경우의 수를 조합하는 코드 (1) ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/10977'>http://www.sysnet.pe.kr/2/0/10977</a> C# - 모든 경우의 수를 조합하는 코드 (2) ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/10978'>http://www.sysnet.pe.kr/2/0/10978</a> </pre> <br /> 일단 모든 경우의 수를 조합하는 코드는 더 이상 할 이야기가 없습니다. 그 정도만 알아도. ^^<br /> <br /> 단지, "<a target='tab' href='http://www.sysnet.pe.kr/2/0/10954'>C# - 조합(Combination) 예제 코드</a>" 글에서는 nCr의 형태로 조합하는 코드를 담고 있는데요. <br /> <br /> 이와 관련해 "해커의 기쁨"이라는 책에 보면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 해커의 기쁨 : 비트와 바이트 그리고 알고리즘 [제2판] ; <a target='tab' href='http://www.yes24.com/24/goods/9218103?scode=032'>http://www.yes24.com/24/goods/9218103?scode=032</a> </pre> <br /> 18페이지에 "Gosper"가 고안했다는 알고리즘이 실려있습니다. 다음은 책의 코드를 C#의 ulong 타입으로 변경한 것입니다. (ulong이기 때문에 n <= 64 범위내에서만 코드가 정상동작합니다.)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } </pre> <br /> 위의 함수는 입력된 x 변수의 값에 포함된 1-비트 개수를 유지하면서, 그것의 바로 다음으로 큰 수를 구해서 반환합니다. 예를 들어, 다음과 같은 역할을 하는 것입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 입력값: 01111 0000 출력값: 10000 0111 </pre> <br /> 따라서, 나머지 처리는 <a target='tab' href='http://www.sysnet.pe.kr/2/0/10977'>C# - 모든 경우의 수를 조합하는 코드 (1)</a> 글에서 했던 것과 유사하게 비트 값에 따른 조합 값만 추리는 작업을 추가하면 nCr 조합을 구할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } } </pre> <br /> 사용은 다음과 같은 식으로 하면 되고,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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(" }"); } } </pre> <br /> 출력값은 이렇습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > { 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, } </pre> <br /> (<a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=1036&boardid=331301885'>첨부한 파일은 이 글의 코드를 포함</a>합니다.)<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
1942
(왼쪽의 숫자를 입력해야 합니다.)