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, 4 } 4개를 element에서 2개를 고르는 k-permutation의 경우에는 다음과 4! / (4 - 2)!개의 permutation이 만들어집니다.

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

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

위에서 두개만 고르는 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이 되어 있지 않은 라인은 리턴하지 않으면 되는 것이죠.

구현은 다음과 같습니다. 여기서 범위가 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

AnonymousAugust 21, 2012 at 7:05 PM
좋은글이네요~ 잘 참고하겠습니다 :)
ReplyDelete
Replies

Add comment

IdeA thinKING

Search This Blog