Combinations and permutations

Combination과 permutation관련된 기능을 가진 C소스입니다. Combination과 Permutation은 기초적인 수학적 구조이면서도 볼수록 흥미로운 구조이죠. MKSeo군 덕분에 애초 2개의 간단한 기능만하던 소스가 여러 기능이 붙었읍니다. 얼떨결에 확장된 기능으로 combination값을 구하는것과 주어진 combination이나 주어진 index에 대해서 서로 변환하는 기능, 주어진 permutation과 주어진 index간의 변환기능, random하게 permutation이나 combination을 구하는 기능이 있읍니다.


Combinations구하기



Permutation 구하기 (순서가 이상한 순서이긴합니다만)



Combination값 구하기(1000_C_30의 값이죠), index로 특정 combination구하기(15_C_5의 2000번째 combination이 3,5,12,14,15임을 얘기해줍니다.), combination으로 index구하기(거꾸로 해당 combination이 2000번째임을 얘기해줍니다.).



역시 permutation을 구하는것입니다. 2번과 다른것은 이것의 순서가 일반적인 정상적인 순서를 구해준다는것이죠. 2번과 비교해보시면 이게 더 깔끔한 순서들을 가지고있음을 볼수 있읍니다. 일반적으로 기대하시는 순서들이죠.


8번은 index에 의해서 특정 permutation을 구해줍니다. 위에서는 7_C_4에서 600번째가 7,5,3,2임을 얘기해주고 있읍니다. 반대로 10번 기능은 주어진 permutation의 index를 찾아줍니다. 9번은 7번과 같은 결과를 내지만, 8번기능을 반복하는것에 불과합니다. 전체 permutation을 찾는 방법으로는 그다지 좋지 않을듯.


11,12번은 랜덤하게 permutation혹은 combination을 찾아줍니다. 11번은 n개에서 하나씩 빼가면서 뽑아내는 방식이고, 12번은 shuffling을 이용한 방식입니다.

1,2번은 recursive하게 주어진 모든 combination이나 permutation을 구할때 적합하며, 3번은 combination값을 빠르게 구하고자할때 적합합니다. 4번은 주어진 index에 의해 특정한 하나의 combination을 찾게해주고, 6번은 거꾸로 주어진 combination이 몇번째인지를 알려줍니다. 5번은 1번과는 다르게 4번방식을 이용해서 모든 combination을 찾아냅니다. (애초에 디버깅용기능이죠. 모든 combination을 찾는데는 좋은 방법이 아닙니다.) 7,8,9,10번 기능도 대동소이하며 permutation에 관련된 기능들입니다.

밑의 소스는 물론 테스트를 대충하였고 버그가 상존하고 있으며-_-; 알고리즘을 실현했다는데에 의의를 둘수 있읍니다. 따라서 readability는 극히 낮으며, 코멘트도 거의 없읍니다. 죄송-_- (별로 원하는 사람도 없어서 말이죠.); 특히 제대로된 input을 넣으시기 바랍니다. 또한 너무 큰 범위의 수를 넣으면 overflow가 마구날테니 적당한 범위의 입력만을 넣으세요.

이 코드가 작성된 배경과-_-; 이 문제에 대한 내용은 여기 쓰레드 를 참고하세요. 이 글의 코멘트로 index로 combination을 찾는것과 그 반대의 경우는 대충 설명되었고, index로 permutation을 찾는것과 그 반대도 비슷한데, 처음에 해당 combination을 찾은이후에는 결국 index를 factorial number system으로 바꾸는것과 같습니다. permutation은 factorial number system을 잘 보여주는 예제로군요. 11번은 무척 큰 N에 대해서 유용할테고 12번은 k가 n과 같거나 비슷할때 빠르게 shuffling하고자 할때 유용합니다. 12번의 shuffling은 TAOCP vol.2에 등장합니다.



소스 코드입니다. -> Source code

Copyright (C) 2003 Lee, Min.