순열, 순서구분하고 선택하는 방법

순열에 아주 좋은 것

http://www.cplusplus.com/reference/algorithm/next_permutation/

next_permutation - C++ Reference

바로 next_permutation 함수다.

 

말 그대로 다음 순열 함수를 반환하는데 (사전순)예를 들어보자

#include <iostream>     
#include <algorithm>   

int main () {
  int myints[] = {1,2,3};

  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );


}

 

결과는???

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

Iterator를 받아서 해당되는 범위에 다음 순열을 만들어준다고 보면 된다.

 

만약 조합이 필요하다면???

예를 들어 1 2 3 4,5에서 수 2개를 순서 없이 뽑아보자

그럴 때에도 이 함수를 이용하면 된다.

바로 0과 1을 이용해 next_permutation을 돌리는 방법으로 해결하면 된다.

5개에서 3개를 뽑는 문제라면 배열 a를 {0, 0, 0, 1, 1}로 두고 돌리면 된다.

 

무슨 뜻이냐..? 하면 1이 뽑을 숫자라는 이야기인데..?

0과 1로 바꿔버리면 어차피 뽑을 숫자가 같이 1,1이면 permutation에서도 중복되는 일이 없기 때문에..?..더 쉽게 말하자면순열에서 (1,5) (5,1)은 다르지만 조합에선 (1,5)로 무조건 같다.

문제를 풀면 더 확실히 이해된다. 백트래킹 문제 풀어보자.