[알고리즘/C++] 순열

순서가 있는 뽑기 → 순열

순서가 없는 뽑기 → 조합

 

순열은 next_permutation 함수를 이용해 구현.

next_permutation은 오름차순 배열이 들어오면, 오름차순으로 순열을 뽑아주는 함수.

next_permutation(a, a+a.length())
next_permutation(a.begin(), a.end())

위 문장처럼 매개변수로 순열의 시작부분과 순열의 끝부분을 넣어주면 된다.

중요한점은 오름차순 배열을 넣어야 한다는 것!

 

(c.f. prev_permutation은 내림차순으로 순열을 뽑아준다.)

 

- 순열 예시

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[] = {2,1,3};
    vector<int> b = {1,2,3};
    
    //sort함수를 이용해 오름차순 정렬
    sort(a, a+3);
    
    // 배열 사용하는 경우
    do{
    	for(int i : a ) cout << i << " ";
        cout << '\n';
    }while(next_permutation(a, a+3)
    
    // 벡터 사용하는 경우
    do{
    	for(int i : b) cout << i << " ";
        cout << '\n';
    }while(next_permutation(a.begin(), a.end()));

 

- 순열 일부만 뽑기

// 두개만 뽑는 경우
#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> a = {30, 70, 50, 20, 60};
    // 오름차순으로 정렬해주기
    sort(a.begin(), a.end());
    do{
    	for(int i = 0; i<2; i++){
        	cout << a[i] << " ";
        }
        cout << '\n';
    }while(next_permutation(a.begin(), a.end());

 

다만 위 코드는 두개가 여러번 출력이 될 것이다.

왜냐하면 두개 외에 나머지 요소들은 뒤에서 계속 정렬되고 있기 때문.

그래서 중복이 된 상태로 계속 출력이 된다.

(예 1,2,3,4,5 -> 1,2,3,5,4 -> 1,2,4,3,5 -> 1,2,4,5,3 ... 이렇게 정렬이 될 동안 앞에 1,2는 위치가 고정되어있음)

 

- 순열 공식 

 

 

문제에서

"순서"에 따라, "순서"를 재배치하여 이란 표현이 나오거나

~한 "순서"의 경우 최대값을 구하시오 등 순서에 대한 결과를 구해야하는 경우

항시 순열을 생각해야한다.