[Java]순열과 다음 순열

*재귀를 이용한 순열 구하기

-> 처음에는, 재귀를 이용하여 모든 순열을 구하였다. 하지만 이전에 공부한 다음 순열을 이용하여도 모든 순열을 구할 수 있다.

sskl660.tistory.com/48

[Java] 순열(Permutation)

sskl660.tistory.com/54

[Java]다음 순열(Next Permutation)

-> 보통 재귀를 이용한 방식은 생각보다 메모리와 시간을 다음 순열을 이용한 방법보다 더 잡아 먹는다. 따라서, 다음 순열을 반복적으로 구하는 과정을 통하여 순열을 구하는 방법을 연습하도록 하자.

 

*다음 순열을 이용한 모든 순열 구하기

-> 첫 순열을 포함하여, (모든 순열의 경우의수(nPn) - 1)번 만큼 다음 순열을 구해준다면 모든 순열을 구할 수 있다.

-> 예를 들어 집합 {1, 2, 3}에서 3개를 선택한 모든 순열을 다음 순열을 이용하여 구현해보자.

package cases;

import java.util.Arrays;

public class Permutation2 {
	static int[] nums = { 1, 2, 3 };

	public static void main(String[] args) {
		// 순열의 총 개수를 구한다.
		int per_num = 1;
		for (int i = 1; i <= nums.length; i++) {
			per_num *= i;
		}
		System.out.println("순열의 총 개수  = " + per_num);

		// 해당 순열의 개수 만큼 다음 순열을 구한다.
		for (Integer num : nums) {
			System.out.print(num + " ");
		}
		System.out.println();
		for (int i = 0; i < per_num - 1; i++) {
			nextPermutation();
			System.out.println();
		}
	}

	private static void nextPermutation() {
		// 주어진 순열의 뒤부터 탐색하며, 증가하는 부분을 찾는다.
		int idx = 0;
		int N = nums.length;
		for (int i = N - 1; i > 0; i--) {
			if (nums[i - 1] < nums[i]) {
				idx = i;
				break;
			}
		}

		// 해당 인덱스를 기준으로, 좌/우지점을 나눈다.
		// 좌측의 제일 오른쪽 숫자에 대하여, 우측의 제일 오른쪽 지점부터 탐색하며 큰 수를 찾는다.
		// 해당 숫자를 찾았다면 각 숫자를 서로 Swap한다.
		for (int i = N - 1; i >= idx; i--) {
			if (nums[idx - 1] < nums[i]) {
				int temp = nums[idx - 1];
				nums[idx - 1] = nums[i];
				nums[i] = temp;
				break;
			}
		}

		// 우측 지점을 정렬한다.
		Arrays.sort(nums, idx, N);

		// 결과 출력
		for (Integer num : nums) {
			System.out.print(num + " ");
		}
	}
}

※ 만일, 주어진 수 부터의 모든 다음 순열을 구하고 싶다면, 일전에 공부한 '다음 순열은 원소가 증가하는 부분이 존재하지 않으면 존재하지 않는다'는 점을 이용하여 구하면 된다.