[Algorithm] 순열 (next_permutation)

✔️순서와 상관 있게 뽑는 것 - 순열

✔️순서와 상관 없이 뽑는 것 - 조합

 

ex) 문제에서 순서를 재배치하여 ... , ~한 순서의 경우 MAX 값을 ...

>> 순열

 

{1,2,3}을 순서와 관계 없이 뽑는다 (조합)

>> {1,2,3} 1개

 

{1,2,3}을 순서와 관계 있게 뽑는다 (순열)

>> {1,2,3} , {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 6개

---

( 오류 ) c++98 mode in Dev-C++ 문제 해결

코드로 구현하고 컴파일을 하니 오류가 뜨는 것이 아니던가!!

[Error] range-based 'for' loops are not allowed in C++98 mode

 dev-c++의 문법이 std-98을 기반으로 하고있기 때문에 뜬다고 한다..

 

( 해결방법 )

tools - compiler Options를 눌러 창을 열고

 Add the following commands when calling the compiler: 에 체크해주고

"-std=c++11" 을 작성해준 뒤 ok 버튼을 누르면 된다

---

💻 순열을 코드로 구현 (next_permutation 사용)

ex) {1,2,3}

#include<bits/stdc++.h>
using namespace std;
int main(){
	int arr[]={1,2,3};
	do{
		for(int i : arr)
		{
			cout << i <<" ";
		}
		cout<<endl;
	}while(next_permutation(&arr[0],&arr[0]+3));
}

>> 1 2 3
   1 3 2
   2 1 3
   2 3 1
   3 1 2
   3 2 1

      1 2 3

-> 0 1 2 3

(from(시작지점), to(끝지점)) to에는 배열의 마지막 부분 다음이 들어가야함 

(&arr[0],&arr[0]+3) -> 시작지점인 1부터 배열의 마지막 부분 다음인 3을 더한 값까지

 

 

- Vector라면? (begin, end)

#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> arr={1,2,3};
	do{
		for(int i : arr)
		{
			cout << i <<" ";
		}
		cout<<endl;
	}while(next_permutation(arr.begin(),arr.end()));
}

>> 1 2 3
   1 3 2
   2 1 3
   2 3 1
   3 1 2
   3 2 1

모든 순열을 반환하면 false가 되어 끝남

 

- 앞에 값이 1이 아닌 2라면?

#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> arr={2,1,3};
	sort(arr.begin(),arr.end());
	do{
		for(int i : arr)
		{
			cout << i <<" ";
		}
		cout<<endl;
	}while(next_permutation(arr.begin(),arr.end()));
}

//sort 전
>> 2 1 3
   2 3 1
   3 1 2
   3 2 1

//sort 후
>> 1 2 3
   1 3 2
   2 1 3
   2 3 1
   3 1 2
   3 2 1

2부터 순열을 찾기 때문에 정확한 값이 나오지 않음

sort를 통해 오름차순으로 정렬해준 뒤 순열을 만들어준다

 

순열은 경우의 수의 합을 공식으로 구할 수 있다!