next permutation

다음 순열에 해당하는 배열을 찾는 방법.

1. 처음부터 순서대로 배열을 보면서 arr[i] < arr[i+1]을 만족하는 가장 마지막 i를 찾는다.
   1. 혹은 맨 뒤에서부터 배열을 보면서 arr[i-1] >= arr[i] 인 마지막 i를 찾는다. 
2. 만약 그러한 i가 없다면 이미 마지막 순열이다.
3. 다음은 끝에서 시작하면서 arr[j] > arr[i] 인 첫번째 j를 찾는다.
4. 이후에 swap(i,j)한다.
5. 그 이후에 i+1부터 끝까지 정렬을 해준다. 정렬을 할 때는 앞뒤만 바꾸는 작업을 해주면 된다. 그 이유는 i+1부터 끝까지는 이미 내림차순이기 때문이다.

이 배열을 예로 들면 1번을 만족하는 i는 숫자 1을 가지고 있는 arr[2]이다. 또한 3번을 만족하는 j는 숫자 7을 가지고 있는 arr[4]이다.
따라서 i = 2, j = 4이 된다. 그 이후에는 4번, 5번 작업을 해주면 된다.

 

이를 코드로 나타내면 다음과 같다.

	static void nextPermutation() {
		int i = -1;
		for (int w = 0; w + 1 < word.length; w++) {
			if (word[w] < word[w + 1])
				i = w;
		}
		if (i == -1)
			return;
		int j = word.length - 1;
		while (j - 1 >= 0 && word[j] <= word[i])
			j--;
		swap(i, j);
		i++;
		j = word.length - 1;
		while (i < j) {
			swap(i, j);
			i++;
			j--;
		}
	}

1-1 방법으로 하면 이런 코드가 된다.

static void next_permutation() {
	int i = arr.length-1;
	while(i-1 >= 0 && arr[i-1] >= arr[i]) i--;
	if(i <= 0) return;
	
	int j = arr.length-1;
	while(j >= 0 && arr[j] <= arr[i-1]) j--;
	swap(i-1,j);
	
	j = arr.length-1;
	while(i < j) {
		swap(i,j);
		i++;
		j--;
	}
}

순열이 같은 숫자를 포함하지 않는다면 j를 구하는 과정에서 =를 빼도 될 것 같다. 만약 같은 수를 포함한다면 =을 포함해야 한다.

 

이를 연습할 문제는 

https://www.acmicpc.net/problem/9081

9081번: 단어 맞추기

이 문제를 풀어보면 된다.