[C++ 순열과 조합] next_permutation

프로그래머스 Level1의 소수 만들기, Level2의 소수 찾기를 풀면서 next_permutation 함수를 사용했습니다.

사용법에 대해 알고 있지만, 자주 사용되는 함수이기도 해서 정리해보려고 합니다.

 

 

 

[순열]

 

수학에서 말하는 순열은 서로 다른 n개의 원소에서 r개를 뽑아서 한줄로 세우는 경우의 수를 의미합니다.

원소를 한줄로 세우지만, 원소의 조합이 같더라도 순서가 다르면 다른 방법입니다.

 

예를 들어서 int arr[3] = {1, 2, 3}의 원소들의 순열을 구하면

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

총 6가지이며, 원소들의 조합은 같지만 순서가 다르기 때문에 다른 방법으로 보는 것을 알 수 있습니다.

 

 

[next_permutation]

 

 

std::next_permutation - cppreference.com

 

C++에서의 algorithm 헤더에는 순열을 구할 수 있는 함수인 next_permutation 함수가 있습니다.

 

template<class BidirIt>
	bool next_permutation(BidirIt first, BidirIt last);
    
template<class BidirIt, class Compare >
	bool next_permutation(BidirIt first, BidirIt last, Compare comp);

 

 

1. next_permutation은 순열을 구할 배열이나 vector, string의 시작(첫번째 파라미터 해당)과 끝(두번째 파라미터 해당)을 넘겨줍니다. 

2.  다음 순열이 존재하면 true를 반환하고 다음 순열이 없는 경우에는 false를 반환하는 형태입니다.

3. do-while문 과 같이 쓰입니다.

 

 

[next_permutation 사용시 주의할 점]

 

1. 순열의 대상(컨테이너(배열, vector, string..))이 오름 차순으로 정렬이 되어 있어야 합니다.

더 큰 순열로 재배열 할 수 있으면 반복하여 순열을 생성하는 구조(operator < 을 이용하여 순열 생성)로 앞에 더 큰 값이 있게 되면 반복하지 않기 때문입니다.

 

2. 중복이 있는 원소들은 중복을 제외하고 순열을 구할 수 있습니다.

 

 

2번을 프로그래머스 소수 찾기의 #입출력 예2로 설명하자면

 

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
    string s = "011";
    do {

        for (int i = 0; i < s.length(); ++i) {
            cout << s[i];
        }
        cout << '\n';

    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

 

string  "011" 의 순열을 구하면 중복을 제외하고,

"011", "101", "110" 을 구할 수 있습니다.

 

 

[next_permutation 사용 예시]

 

 

[{1, 2, 3}의 모든 순열 구하기]

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;


int main(void)
{
    vector<int> arr = { 1,2,3 };
    do {

        for (int i = 0; i < arr.size(); ++i) {
            cout << arr[i];
        }
        cout << '\n';

    } while (next_permutation(arr.begin(), arr.end()));
    return 0;
}

 

 

[결과]

123
132
213
231
312
321

 

 

[조합]

수학에서 말하는 조합은 서로 다른 n개의 원소에서 r개를 뽑아서 만드는 부분집합을 의미합니다.

순열은 순서를 중요시 했지만 조합에서의 순서는 중요하지 않습니다.

 

예를 들어 {1,2,3}에서 2개를 뽑는 조합을 구한다면

{2,3}

{1,3}

{1,2}

총 3가지이며 순열과는 다르게  {1, 3} = {3, 1}, {1,2} = {2,1}, {2,3} = {3,2}이 동일한 것으로 봅니다.

 

 

[next_permutation 이용하여 조합  구하기]

 

A vector의 n개의 원소들 중 r개를 뽑기 위한 방법은 다음과 같습니다.

 

1. 크기가 n개인 boolean 자료형의 temp vector를 생성합니다.

2. temp vector를 n-r개는 false로 채우고, r개는 true로 채웁니다.

3. temp vector의 순열을 구합니다.(next_permutation)

4. temp vector의 원소가 true인 경우에만 A vector의 값을 가져옵니다.

 

 

[next_permutation 이용하여 조합  구하기 사용 예시]

 

[{1, 2, 3}에서 2개를 뽑는 조합 구하기]

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;


int main(void)
{
    vector<int> arr = { 1,2,3 };
    int len = arr.size();
    vector<bool> temp(len);
    fill(temp.end() - 2, temp.end(), true);
    do {

        for (int i = 0; i < arr.size(); ++i) {
            if(temp[i])
                cout << arr[i];
        }
        cout << '\n';

    } while (next_permutation(temp.begin(),temp.end()));
    return 0;
}

 

 

[결과]

23
13
12