[STL] next_premutation() (STL 순열 )

• 순열, next_permutation

 

c++ STL에서는 순열과 조합을 만들어주는 함수를 제공합니다.

두 함수는 <algorithm> 라이브러리에 존재합니다.

 

 

순열, next_permutation

 

순열을 만들어주는 next_permutation.

 

bool next_permutation(vec.begin(),vec.end());

인자로 넘겨진 반복자를 이용해 순열의 형태로 정렬한 후 true를 반환합니다, 더 이상 순열의 형태로 정렬할 수 없다면 false를 반환합니다.

 

또 이 함수는 중복을 제외하며 <연산자를 이용해 순열의 형태로 정렬하기에 오른차순을 만들고 사용하여 합니다. < 비교 연산에서 false가 나면 그 값보다 작은 수의 순열은 다 만들었다 판단합니다. 내림차순이 다 만들어지면 더이상 구할 순열이 없다 판단하고 false를 반환합니다.

 

nPn을 구하기 위해선 아래 코드처럼 접근하면 됩니다.

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};

	do
	{
		for(int i = 0; i < v.size(); i++)
		{
			cout << vec[i] << " ";
		}
		cout << '\n';

	}while(next_permutation(vec.begin(),vec.end()));   

}

 

nPr을 구하기 위해선 아래와 같이 접근하면 됩니다.

 

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};
    	int n = vec.size(); 
    	int r = 2  
	
	do
	{
	    for(int i = 0; i < r; i++) cout << vec[i] << " ";
	    cout << '\n';

    	reverse(vec.begin() + r, vec.end());

	}while(next_permutation(vec.begin(), vec.end()));   

}

잘 이해가 안 갈 수 있는데 5P2를 구한다하면 출력의 예가 {1 2} , {1, 3} , {1, 4} ... 이런식으로 나올 것 입니다.\

위의 코드를 진행하면 기존 nPn의 경우 12345, 12354 ... 이런 식으로 출력이 되었을 테지만

5P2인 경우를 구함으로 12가 접두사인 순열들을 처음 하나만 만들고 뒤에 것 들은 만들지 않습니다.

그렇게 되면 12가 접두사인 순열이 {1, 2}만을 하나 만들고 13이 접두사인 순열을 만드는데 이것도 하나만 만듭니다.

그렇게 함으로 {1 2}, {1 3}, {1 4} ... 와 같은 nPr을 구현할 수 있는 것 입니다.