Skip to main content

C++ of the Day #35 - k-permutation, k-combination

C++의 algorithm 라이브러리에는 N!개의 permutation을 구할 수 있는 next_permutation과 prev_permutation 함수가 존재합니다. 하지만 N개의 element들중에 k개를 구하는 k-permutation에 대한 함수는 제공하지 않죠. 이번 글에서는 k-permutation을 위한 함수를 만들어 보겠습니다.

먼저 permutation의 예를 들어 보면 다음과 같습니다. { 1, 2, 3 }과 같이 3개의 element를 가지고 next_permutation을 하면 다음과 같이 3!개의 permutation이 만들어집니다.


1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


다음으로 { 1, 2, 3, 4 } 4개를 element에서 2개를 고르는 k-permutation의 경우에는 다음과 4! / (4 - 2)!개의 permutation이 만들어집니다.


1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3


마지막으로 { 1, 2, 3, 4 }의 4개를 가지고 2개를 순서에 상관 없이 고르는 k-combination의 경우에는 다음과 4! / (2! * (4 - 2)!)개의 combination이 만들어집니다.


1 2
1 3
1 4
2 3
2 4
3 4


그럼 이제 k-permutation을 위한 next_k_permutation 함수에 대해 먼저 살펴 보겠습니다. 만약 4개의 element를 가지고 next_permutation을 한다면 다음과 같은 결과가 나올 것입니다.


1 2 3 4 <<
1 2 4 3
1 3 2 4 <<
1 3 4 2
1 4 2 3 <<
1 4 3 2
2 1 3 4 <<
...


위에서 두개만 고르는 k-permutation은 << 표시가 된 라인만 리턴하도록 구현되어야 합니다. 따라서 N개에서 k개를 고르는 k-permutation을 구현하기 위해서는 입력된 구간의 [first + k, last) 영역을 역으로 sorting한 후 next_permutation을 호출하면 됩니다. ((next_k_permutation은 sorting을 사용하므로 next_permutation과는 달리 O(N log(N) ) complexity를 가집니다.)) 즉, { 1 2 3 4 } 다음에 올 2-permutation을 구하기 위해서는 { 3 4 }를 역으로 sorting한 후 next_permutation을 호출해 줍니다. 따라서 { 1 2 3 4 } 다음은 { 1 2 4 3 }의 next_permutation인 { 1 3 2 4 }가 되고 이 다음은 { 1 3 4 2 }의 next_permutation인 { 1 4 2 3 }이 됩니다. 다음 표를 참고하세요.

|_. 역순 소팅 |_. OP |_. 다음 값 |
| - | - | (12)34 |
| 12(43) | next_permutation | (13)24 |
| 13(42) | next_permutation | (14)23 |
| 14(32) | next_permutation | (21)34 |
| 21(43) | next_permutation | (23)14 |

Comp를 사용하지 않는 std::next_permutation 버전은 less<>를 사용하기 때문에 Comp를 사용하지 않는 next_k_permutation에서는 역으로 sorting하기 위해 greater<>를 사용합니다.


template
bool next_k_permutation(RandomAccessIterator first,
RandomAccessIterator last,
size_t k)
{
typedef typename
std::iterator_traits::value_type value_type;

std::sort(first + k, last, std::greater());
return std::next_permutation(first, last);
}


다음으로 비교를 위한 함수인 Comp를 입력받는 next_k_permutation의 경우에는 다음과 같이 구현됩니다. 당연하게도 역순으로 sorting하기 위해 !comp(_1, _2)를 사용해서는 안됩니다. less<>의 !(not)은 greater<>가 아니라 greater_equal<>이기 때문이죠. 따라서 여기서는 tr1::bind를 사용하였습니다.


template
bool next_k_permutation(RandomAccessIterator first,
RandomAccessIterator last,
size_t k,
StrictWeakOrdering comp)
{
using namespace std::tr1::placeholders;
using std::tr1::bind;

typedef typename
std::iterator_traits::value_type value_type;

std::sort(first + k, last, bind(comp, _2, _1));
return std::next_permutation(first, last, comp);
}


prev_k_permutation은 next_k_permutation과 거의 동일하므로 설명을 생략하고 다음으로 next_k_combination에 대해 알아보겠습니다. 위에서 살펴 봤듯이 k_permutation은 고르는 순서가 중요하기 때문에 중복된 set을 리턴합니다. 예를 들어 { 1, 2 }와 { 2, 1 }이 따로따로 리턴됩니다. 하지만 이를 set으로 간주하여 순서에 관계없이 k개를 고를때 사용할 수 있는 것이 next_k_combination입니다.

이 함수는 next_k_permutation을 사용하여 [first, first + k)의 범위가 sorting되어 있는 경우에만 리턴하도록 하여 간단히 구현할 수 있습니다. 즉, 아래의 k-permutation에서 << 표시가 된 라인과 같이 sorting이 되어 있지 않은 라인은 리턴하지 않으면 되는 것이죠.


1 2
1 3
1 4
2 1 <<
2 3
2 4
3 1 <<
3 2 <<
3 4
4 1 <<
4 2 <<
4 3 <<


구현은 다음과 같습니다. 여기서 범위가 sorting되었는지 확인하기 위해 사용한 is_sorted 함수는 표준 C++ 라이브러리의 일부가 아니라 표준 이전의 헤더 파일인 에 존재하는 함수입니다. 표준이 아니므로 이를 사용하지 않고 직접 구현해서 사용할 수도 있었으나 어차피 algo.h를 대부분의 컴파일러에서 지원하므로 그냥 이 함수를 가져다 사용하였습니다. ((이것이 컴파일러 벤더가 deprecated로 표시된 함수더라도 다음 버전에서 완전히 뺄 수 없는 이유지요. backward compatibilty가 발목을 잡는 것이죠. :-) ))


template
bool next_k_combination(RandomAccessIterator first,
RandomAccessIterator last,
size_t k)
{
while (next_k_permutation(first, last, k)) {
if (is_sorted(first, first + k)) return true;
}

return false;
}


next_k_combination의 comp를 받는 버전과 prev_k_combination에 대한 설명은 생략하겠습니다. 자세한 내용은 소스 코드를 다운로드받아 직접 보실 수 있습니다.

Downloads



k_algo.tgz

Comments

  1. 좋은글이네요~ 잘 참고하겠습니다 :)

    ReplyDelete

Post a Comment

Popular posts from this blog

1의 개수 세기 - 해답

벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P 그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log 10 n)이라고 적었어야 했네요. 죄송합니다. ... 문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다. 예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다. 이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다. 234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다. 이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다. 한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1

std::map에 insert하기

얼마전 회사 동료가 refactoring한 코드를 열심히 revert하고 있어서 물어보니 다음과 같은 문제였습니다. 원래 코드와 refactoring한 코드는 다음과 같더군요. nvp[name] = value; // original code nvp.insert(make_pair(name, value)); // refactored 아시겠지만 위의 두 라인은 전혀 다른 기능을 하죠. C++03에 보면 각각 다음과 같이 설명되어 있습니다. 23.1.2/7 Associative containers a_uniq.insert(t): pair<iterator, bool> inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place and the iterator component of the pair points to the element with key equivalent to the key of t. 23.3.1.2/1 map element access [lib.map.access] T& operator[](const key_type& x); Returns: (*((insert(make_pair(x, T()))).first)).second. 원래 코드는 매번 새 값으로 이전 값을 overwrite했지만 새 코드는 이전에 키가 존재하면 새값으로 overwrite하지 않습니다. 따라서 원래 기능이 제대로 동작하지 않게 된것이죠. 그래서 물어봤죠. "왜 이렇게 했어?" "insert가 성능이 더 좋다 그래서 했지." :-? 사실 Fowler 아저씨는 Refactoring 책에서 refactoring은 성능을 optimizing하기 위한 것이 아니다라

C++ of the Day #9 - Boost.Python 사용하기 #1

Python 은 가장 인기있는 interpret 언어중의 하나입니다. Python의 장점 중 하나는 C/C++ 모듈과 쉽게 연동할 수 있다는 점입니다. 물론 손으로 일일히 wrapper를 만드는 것은 손이 많이 가고 에러를 만들수 있는 작업이나 SWIG 등과 같은 도구를 사용하면 쉽게 python 모듈을 만들 수 있습니다. Boost.Python 은 이런 SWIG와 같이 python 모듈을 쉽게 만들 수 있도록 도와주는 라이브러리로 순수 C++만을 사용한다는 점이 SWIG와 다른 점입니다. 그리고 개인적으로는 Boost 라이브러리에 포함되어 있는 것들이 왠지 좀 더 믿음직스러워서... :-) 이번 글에서는 Boost.Python 문서에 나와 있는 예제 를 가지고 간단하게 python 모듈을 만드는 방법에 대해서 알아보겠습니다. Requirements 리눅스 이 글에서는 리눅스 환경에서의 사용 방법을 설명한다. Boost.Python 라이브러리 (1.33.1) Boost 라이브러리를 다운로드받아 아래와 유사한 명령으로 라이브러리를 빌드한다. bjam -sTOOLS=gcc -with-python install bjam의 --prefix 옵션으로 라이브러리가 설치될 위치를 변경할 수 있다. Python 라이브러리 (2.4.3) Python을 다운로드 받아 빌드하여 설치한다. 위의 경우와 유사하게 configure의 --prefix 옵션으로 설치될 위치를 변경할 수 있다. Write C++ Code 다음과 같이 코드를 작성한다. // greet.cpp #include <stdexcept> char const* greet(unsigned x) { static char const* const msgs[] = { "hello", "Boost.Python", "world!" }; if (x > 2) throw std::range_error("