자료구조
순열
까르르꿍꿍
2022. 1. 12. 15:34
순열 함수 next_permutation 이 있고 이를 구현해보겠다.
일단 순열을 구할려면
1.a[i-1]<a[i] 를 만족하는 가장 큰 i를 찾는다.
2.j>=i이면서 a[j]>a[i-1]를 만족하는 가장 큰 j를 찾는다.
3.a[i-1]과 a[j]를 스왑 한다.
4.a[i]부터 순열을 뒤집는다.
예를 들어
7 2 3 6 5 4 1 이 있다. 여기서 1번 과정을 거치면
7 2 3 6 5 4 1 3이 가장 큰 i가 된다.그리고 2번 과정을 거치면
7 2 3 6 5 4 1 4가 가장 큰 j가 된다. 그리고 스왑하면
7 2 4 6 5 3 1 이 되고 여기서 4번 과정을 거치면
7 2 4 1 3 5 6 가 되면서 7 2 3 6 5 4 1 의 다음 순열이 된다.
코드를 보자
#include <iostream>
using namespace std;
void swap(int &a,int &b){ //참조에 위한 호출
int temp=a;
a=b;
b=temp;
}
bool next_permutation(int *a , int n){
int i=n-1;
while(i>0 && a[i-1]>=a[i])i-=1; //뒤에서 부터 내림차순이 아니게 될 때를 구함
if(i<=0) return false; //없으면 순열의 끝
int j=n-1;
while(a[j]<=a[i-1]) j-=1; //다시 뒤에서 부터 내림차순 아니게 될떄 까지 반복하며 값이 더 클 때 까지 반환
swap(a[i-1],a[j]); //바꿔줌
j=n-1;
while(i<j){
swap(a[i],a[j]); //남은 거도 오름차순이 되게 다 바꿔줌
i+=1;j-=1;
}
return true;
}