순열과 조합 (C++)

 

[ n개의 숫자를 전부 사용해서 만들 수 있는 모든 순열의 갯수]

 

ex)

1,2,2 가 input으로 들어오면

 

1,2,2

2,1,2

2,2,1

 

3가지가 나온다. 여기서 중요한 점은 "중복된 순열은 제거" 된다는 점이다.

1,2( 1th ) , 2( 2th )   

1, 2( 2th ) , 2( 1th ) 

이런식으로 사실 상 같은 순열이 2번 추출되면 안된다는 뜻이다.

 

이때 사용하는게 바로 C++ 헤더 중 #include<algorithm> 으로 사용할 수 있는 next_permutation이다.

우리가 원하는 결과 값은

 

1,2,2

2,1,2

2,2,1

 

이렇게 3개인데, next_permuation( vec.begin(),vec.end() ) 이 메소드가 하는 역할은 vec를 중복되지 않은 다음 순열 값으로 변경해주는 것이다.

처음 next_permutation이 호출되면 vec의 값이

1,2,2 -> 2,1,2 로

두번째로 next_permuation이 호출되면 vec의 값이

2,1,2 -> 2,2,1 로 바뀐다.

우리는 첫 순열인 1,2,2 도 필요하기에 do - while문으로 다음과 같이 구현해주면 된다.

 

아래는 string이 input의 데이터 타입으로 들어왔지만, arr, string, vector 등 전부 사용 가능하다.

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

//vec :   1,2,3
//next_permutation( vec.begin(), vec.end() ) ->  1,2,3 의 모든 순서쌍을 순차적으로 탐색 (nPn), 단 중복은 자동제거
//  미리 오름차순 정렬이 되어있어야한다!!
// ( 중복제거기에 1,0,0 -> 1,0(1th),0(2th)  1,0(2th),0(1th)
//1,2,3
//1,3, 2



int main()
{
    std::string s = "122";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while (std::next_permutation(s.begin(), s.end()));
}

/* OUTPUT */
/* 112    */
/* 121    */
/* 211    */

 

 

[n개의 수 로 만들 수 있는 모든 숫자]

n개의 수를 통해 만들 수 있는 모든 숫자의 경우의 수는 어떻게 구할 수 있을까?

(ex)

1,2,3 으로 만들 수 있는 모든 숫자는?

 

1

2

3

1,2

1,3

........

3,2,1

 

이런식으로 모든 경우의 수를 고려하는 것인데,  위에서 배운 것을 활용하면 금방 해결할 수 있다.

"n개의 숫자로 만들 수 있는 모든 숫자" 를 수식적으로 표현하면 nP1 , nP2, ..... nPn 까지 모든 경우의 수를 찾는 것이다.

따라서 next_permutation을 사용하되, 그 순열에서 1자리만, 2자리만,..... n자리만 사용하되, 중복을 제거하면 된다.

중복을 제외하는 이유는 다음과 같다

 

next_permutation을 통해 나온 2개의 순열

4,3,2,1

4,2,3,1

에서, 1자리만 뽑으면 각각

1이 나오고, 이는 중복된다.

 

따라서 set이나 visit 배열을 통해 중복값을 검출해주면 해결할 수 있다.

 

 

string str="312";
sort(str.begin(),str.end() ); //next_permutation은 정렬 필수
set<string> nums;
int n = str.size();
string sub;
do {
    for (int i = 1; i <= n; i++)
    {
        sub = str.substr(0, i);   // 정해진 n개의 숫자를 1,2,3,....n개 추출
        nums.insert(sub);
    }
} while (next_permutation(str.begin(), str.end())); // n개의 숫자로 가능한 모든 순열 탐색

 

[순서 상관 없이 선택하기]

흔히 수학에서 조합, Combination으로 불리며 nCr 의 기호로 사용된다. n개 중 순서를 고려하지 않고 3개를 뽑을 때의 경우의 수를 모두 구하는 것인데,

마찬가지로 next_permutation 메소드로 구현 가능하다.

next_permutation은 중복된 순열을 자동 제거해주는데, 이 특성을 활용해보자.

5개 중 3개를 순서 상관없이 선택하는 5C3의 경우 [0,0,1,1,1]의 배열을 next_permutation으로 탐색하면 된다.

여기서 0은 선택하지 않을 2개를 고르는 것, 그리고 1은 선택할 3개를 고르는 것이다.

(ex)

[0,0,1,1,1] 는 0,1번째 idx의 수 는 선택하지 않고, 2,3,4번째 idx의 수를 선택한다는 의미이다.

 

만약 1,2,3,4,5 중 3개를 고르고 싶을 때, 1,2,3,4,5를 next_permutation으로 돌린다면

1,2,3 != 3,2,1 과 같이 순서 쌍이 고려되지만, 고르는 3가지를 1이라고 가정하고 해결한다면 

11100 == 11100 처럼 순서를 무시할 수 있다.

int main()  //nCr 구하기 -> 중복값 제거되는 것을 활용
{
    int arr[5] = { 0, 0, 1, 1, 1 };   //ex) 5개중 3개 뽑기.
    sort(arr, arr + 5);
    do {
        for (int elem : arr) {  
            std::cout << elem;
        }
        std::cout << '\n';
    } while (next_permutation(arr, arr + 5));
}

// OUTPUT
// 00111
// 01011
// 01101
// 01110
// 10011
// 10101
// 10110
// 11001
// 11010
// 11100

 

 

 

 

[실전 문제]

번외로, 이번에 순열과 조합에서 next_permutation을 사용한 풀이만 공개했는데, 아래와 같이 재귀로 조합을 구현할 수 도 있다. 로직을 직접 구현하는 것이기에 유동적인 상황에서 응용하기는 쉽지만, 코드 자체는 더 길어 시간이 지체될 수 있기에 마지막에 소개한다.

재귀함수를 통해 n째 값을

뽑을 때, 뽑지 않을 때

2가지로 나누어 가지를 나누어가며 재귀를 돌면 해결할 수 있다.

#include <iostream>
#include <vector>

using namespace std;
vector<vector<char>> combs;
void Combination(vector<char> arr, vector<char> comb, int r, int index, int depth)
{//depth: n개의 목록들 중 몇번째꺼 탐색중?
//index: 현재 몇번째 까지 선택했는가 (총 r개 선택) 
    if (r == 0)
    {
        combs.push_back(comb);
       
    }
    else if (depth == arr.size())  // depth == n // 계속 안뽑다가 r 개를 채우지 못한 경우는 이 곳에 걸려야 한다.
    {
        return;
    }
    else
    {
        // arr[depth] 를 뽑은 경우
        comb[index] = arr[depth];
        Combination(arr, comb, r - 1, index + 1, depth + 1);

        // arr[depth] 를 뽑지 않은 경우
        Combination(arr, comb, r, index, depth + 1);
    }
}

int main()
{//nCr

    vector<char> vec = { 'a', 'b', 'c', 'd', 'e' };  //뽑을 데이터 목록 (n 의 데이터 목록)

    int r = 3;
    vector<char> comb(r); //nCr 에서 선택한 r을 누적하며 넘겨줄 자료구조  (r 을 구하는 곳)

    //
    Combination(vec, comb, r, 0, 0);  // {'a', 'b', 'c', 'd', 'e'}의 '5C3' 구하기 
   
    return 0;
}

예제 문제

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

 

next_permutation을 통한 완전탐색으로 해결할 수 있는 문제다.

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

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string str = "ACFJMNRT"; //이미 사전순으로 정렬됨.
map<string, bool> ma; //bool 디폴트= false
int solution(int n, vector<string> data) {
    int answer = 0;
    ma.clear();
    str = "ACFJMNRT";
    vector<map<char, int> >v;
    // sort(str.begin(),str.end());
    int cnt = 0;
    do {
        map<char, int> tmp;
        for (int i = 0; i < str.size(); i++)
            tmp[str[i]] = i;
        v.push_back(tmp);
    } while (next_permutation(str.begin(), str.end()));
    int cnt2 = 0;
    for (int j = 0; j < v.size(); j++) {
        bool chk = true;
        for (int i = 0; i < data.size(); i++) {
            char a = data[i][0], b = data[i][2], cmd = data[i][3];
            int num = (int)data[i][4] - 48;
            int dif = v[j][a] - v[j][b];
            if (dif < 0) dif = (-1) * dif;
            dif--;//차이가 i ==간격이 i-1
            if (cmd == '=') {
                if (dif != num) {

                    chk = false;
                    break;
                }
            }
            else if (cmd == '>') {

                if (dif <= num) {
                    chk = false;
                    break;
                }
            }
            else if (cmd == '<') {

                if (dif >= num) {
                    chk = false;
                    break;
                }
            }
        }
        if (chk == true)
            answer++;
    }
    return answer;
}