[개념정리] STL _ 순열구하기 permutation

 

<algorithm> 헤더파일을 추가하여 순열을 자동으로 구해줄 수 있다.

​

 

필요성 :

알고리즘 문제를 풀며 위 함수의 필요성을 느끼게 되었다. 모든 경우에 대해 순열을 바꿔주어 입력을 넣어줘야되는데 일일히 넣어주기는 귀찮았다. permutation 함수를 써서 자동으로 모든 순열을 구할 수 있었다.

(1 2 3 4로 기본 순서가 정해져있었다면 1 2 4 3 / 1 4 2 3 / 1 4 3 2 / 2 1 3 4 등 모든 순열을 구함)

​

- next_permutation : 현재 나와있는 수열에서 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 flase를 반환

​

- prev_permutation : 현재 나와있는 수열에서 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면 false를 반환

 

 

기본구조 :

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare compare);

bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare compare);

 

 

사용 :

do while을 이용한 사용방법이 주로 사용된다.

v[10] = {1,2,3,4};

do{

	for(int i=0; i<4; i++){
    
		cout << v[i] << " ";
        
	}
    
	cout << '\n';
    
}while(next_permutation(v.begin(),v.end()));

// 1234 1243 ... 순서가 될것이다.

v[10] = {4,3,2,1};

do{

	for(int i=0; i<4; i++){
    
		cout << v[i] << " ";
        
	}
    
	cout << '\n';
    
}while(prev_permutation(v.begin(),v.end()));

// 4321 4312 ... 순서가 될것이다.

 

---

 

응용 사용방법 : 

 

만약 vector v 가 아래와 같이 생성되어 있다고 생각해보자

1

2

3

4

5

6

7

8

9

0

이 벡터에서 임의로 3개씩을 선택해야 한다면

 

우선 next_permutation(v.begin(), v.end()) 로 사용할 수 있을 것이다.

 

이후 v[0] v[1] v[2] 를 이용해 3개를 선택한다면 다음과 같은 문제가 발생할 것이다.

 

permutation 사용시

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

6

7

8

0

9

1

2

3

4

5

6

7

9

8

0

 

이와 같이 바뀌었음에도 v[0] v[1] v[2] 는 모두 1 2 3 으로 동일하다.

 

다른 방식으로 이 세 개를 섞어야만 할 것이다.

 

temp를 사용해 섞기

 

temp.resize(v.size());
for (int i = 0; i < temp.size(); i++) {
	temp[i] = 0;
}
for (int i = 0; i < M; i++) {
	temp[i] = 1;
}
sort(temp.begin(), temp.end());

do{
    /*
	만약 temp가 1이라면	
    그 때의 인덱스가 v의 인덱스를 참조한다
    */
}while (next_permutation(temp.begin(), temp.end()));

 

temp 배열

0

0

0

0

0

0

0

1

1

1

과 같이 생성해 놓고 temp를 permutation으로 섞어주면

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

1

1

0

1

0

0

0

0

0

0

1

1

1

0

와 같이 섞이게 된다.

 

이 후 값이 1인 인덱스를 v에 대입해 주면 랜덤의 값을 선택할 수 있을 것이다.