순열과 조합 C++

순열과 조합 개념과 차이점

 

순열(Permutation) : 순서를 정해서 나열

ex) 1,2,3 중에서 두개를 뽑아 나열할 경우 : {1,2}, {1,3}, {2,3}, {2,1}, {3,1}, {3,2} 

 

조합(Combination) : 순서가 정해지지 않은 집합들의 모음들, 뽑기

ex) 1,2,3 중에서 두개를 뽑을 경우 : {1,2}, {1,3}, {2,3}

 

차이점 : 순열은 순서가 중요하고 조합은 순서 상관없다. 예를 들어 수열 같은 경우 {1,2} , {2,1} 은 다르지만 조합의 경우 원소가 1,2로 같기 때문에 {1,2} 하나로 생각한다.

---

순열 구현

1. C++ algorithm 라이브러리의 next_permutation, prev_permutation 사용

*next_permutation : 오름차순

*prev_permutation : 내림차순

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

void printV(vector<int> &v)
{
	for(int i = 0; i < v.size(); i++)
			cout << v[i] << " ";
	cout << "\n";
}
int main()
{
    int a[3] = {1, 2, 3};
    vector<int> v;
    for(int i = 0; i < 3; i++)
        v.push_back(a[i]);
        //1, 2, 3부터 오름차순으로 순열을 뽑습니다.
    
    do
        printV(v);
    while(next_permutation(v.begin(), v.end()));

    cout << "-------------" << '\n';
    v.clear();
    for(int i = 2; i >= 0; i--)
        v.push_back(a[i]);
        //3, 2, 1부터 내림차순으로 순열을 뽑습니다.
    do
        printV(v);
    while(prev_permutation(v.begin(), v.end()));
    
    return 0;
}

 

2. DFS 로 구현

#include <iostream>

using namespace std;

int n=5; //n개 중에
int r=2; //r개 뽑기

int arr[5]={1,2,3,4,5};
bool visited[5];
vector<int> vec;

void permutation(int depth){
    if(depth==r){
        for(int i=0;i<r;i++){
            cout<<vec[i];
        }
        cout<<"\n";
    }
    for (int i = 0; i < n; i++)
    {
        if(!visited[i]){
            vec.push_back(arr[i]);
            visited[i]=true;
            permutation(depth+1);
            visited[i]=false;
            vec.pop_back();
        }
    }
    
}

int main(){
    permutation(0);
}

 

 

3. swap 활용

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

//n개중에 r개를 뽑는다.
void permutation(int n,int r,int depth){
    if(r==depth){
        for (int i=0;i<r;i++)
        {
            cout<<v[i];
        }
        cout<<"\n";
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(v[i],v[depth]);
        permutation(n,r,depth+1);
        swap(v[i],v[depth]);
    }
    return;
}

int main(){
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    permutation(3,2,0);
    
}

---

조합 구현

1. C++ algorithm 라이브러리의 next_permutation, prev_permutation 사용

bool vecto인 temp를 이용해서 각 원소를 나타낼지 (true), 안나타낼지(false) 결정

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int r=2;
vector<int> vec;
vector<bool> temp(5,true);

int main(){
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(5);
    for(int i=0;i<vec.size()-r;i++){
        temp[i]=false;
    }

    do{
        for (int i = 0; i < vec.size(); i++)
        {
            if(temp[i]){
                cout<<vec[i]<<" ";
            }
        }
        cout<<"\n";
        
    }while(next_permutation(temp.begin(),temp.end()));
}

 

2. DFS로 구현

idx는 화살표가 오른쪽 방향으로만 향하게 하도록 한다. 

visited 배열은 '중복 방지'역할을 한다.

visited를 활용해서 출력할지 안할지 결정한다.

#include <iostream>

using namespace std;

bool visited[5];
int arr[5]={1,2,3,4,5};
int n=5; //n개중에
int r=2; //r개 뽑기

void dfs(int idx,int depth){
    if(depth==r){
        for (int i = 0; i < 5; i++)
        {
            if(visited[i]){
                cout<<arr[i];
            }
        }
        cout<<"\n";  
        return; 
    }

    for(int i=idx;i<n;i++){
        if(visited[i]) continue;
        visited[i]=true;
        dfs(i,depth+1);
        visited[i]=false;
    }
}

int main(){
    dfs(0,0);
}

---

중복 순열, 중복 조합

1. 중복 순열 구현

순열 dfs 코드에서 select 배열 지우기

#include <iostream>
#include <vector>

using namespace std;

int arr[5]={1,2,3,4,5};
vector<int> vec;
int n=5;
int r=2;

void dfs(int depth){
    if (depth==r)
    {
        for (int i = 0; i < vec.size(); i++)
        {
            cout<<vec[i];
        }
        cout<<"\n";
        return;
    }

    for (int i = 0; i < n; i++)
    {
        vec.push_back(arr[i]);
        dfs(depth+1);
        vec.pop_back();
    }
    
    
}
int main(){
    dfs(0);
}

 

2. 중복 조합

조합 dfs 코드에서 select 배열 지우기

#include <iostream>
#include <vector>

using namespace std;

int arr[5]={1,2,3,4,5};
vector<int> vec;
int n=5;
int r=2;

void dfs(int depth,int idx){
    if(depth==r){
        for(int i=0;i<vec.size();i++){
            cout<<vec[i];
        }
        cout<<"\n";
        return;
    }

    for (int i = idx; i < n; i++)
    {
        vec.push_back(arr[i]);
        dfs(depth+1,i);
        vec.pop_back();
    }
    
}

int main(){
    dfs(0,0);
}

 

---

DFS로 구현할 때 차이점

	visited	depth	idx
중복 조합	X	O	X
조합	O	O	X
중복순열	X	O	O
순열	O	O	O