참고
Next Permutation
NOTE
어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다!
다음의 수열은 뭐가 나와야 하는가?
ex) 231이 주어지면 312를 구해야한다.
알고리즘
NOTE
어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다!
1. idx -1에서 역순으로 숫자가 감소하는 구간이 있는지 탐색한다. (A)
2. idx -1에서 역순으로 A보다 큰 값이 나오기 전까지 탐색한다. (B)
3. A와 B를 스왑한다.
4. B 이후의 배열을 역정렬한다.
void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 감소하는 구간 찾기
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 다시
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
Java
복사
특징
NOTE
장점
•
재귀로 짜여진 순열과 달리 시간 복잡도가 낮다
•
재귀적인 호출이 없을 뿐더러, 각각의 순열에 대해서 자연스레 백트래킹 과정이 있고, 하나의 배열로 각 인덱스 값만 교체해주므로 훨씬 빠름
단점
•
원래의 배열을 재배열하여 순열을 뽑으므로 nPr과 같이 특정 개수의 순열은 뽑아내지 못한다.
•
nPr과 nCr 같은 알고리즘으로 만들어낼 수 있음