[알고리즘] Next Permutation

 

 

 Next Permutation 

개요

Next Permutation 은 순열과 조합을 구하는 또 하나의 방법입니다.

1 2 3 의 숫자를 가지고 순열을 만들기
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

1, 2, 3 의 숫자를 가지고 만들 수 있는 순열은 위와 같습니다.

보통 자연스럽게 순열을 구하고자 할 때 저렇게 구하는 편이 많습니다.

앞에 놔두고 뒤에 숫자들을 바꾸고.. 앞에 자릿수의 순열이 끝나면 다음 자릿수의 숫자를 젤 앞으로 가지고 와서 

나머지 자릿수를 또 순열로 만들고..

이러한 방법을 나타난 것이 바로 next permutation 입니다.

 

 

순열

package lecture;


import java.util.Arrays;


public class Test {
	static int N = 3;
	static int[] tgt = { 1, 2, 3 };
	static int cnt;


	public static void main(String[] args) throws Exception {
		// n! = 3 x 2 x 1 = 6 가지

		Arrays.sort(tgt);
		System.out.println("tgt[]: " + Arrays.toString(tgt));

		while (true) {
			System.out.println(Arrays.toString(tgt));
			cnt++;
			if (!np()) break;
		}

		System.out.println("총 가짓 수 : " + cnt);

	} // end main


	private static boolean np() {
		int i = N - 1;
		int j = i;
		int k = i;

		while (i > 0 && tgt[i - 1] >= tgt[i]) i--;

		if (i == 0) return false;

		while (tgt[i - 1] >= tgt[j]) j--;
		swap(tgt, i - 1, j);

		while (i < k) swap(tgt, i++, k--);

		return true;

	} // end np


	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	} // end swap
}

출력

처음에 오름 차순으로 정렬을 해야합니다. 그러면 1 2 3 이 제일 처음 찍히게 됩니다.

np() 에서 1 2 3 은 swap(tgt, i-1, j) 에서만 걸리게 됩니다. 따라서 1 3 2 가 다음으로 찍힙니다.

그리고 나서 그 다음에는 첫번째 while 에 걸리게 돼서 i--; 이 실행됩니다.

따라서 1 과 2 가 swap 이 되어 2 3 1 이 되고 세번째 while 문에 걸리게 되어 첫번째 숫자 2 를 제외하고 정렬이 되어 2 1 3 이 됩니다.

이런식으로 순열을 만들게 됩니다.

next permutation 의 순열은 가지고 있는 배열에서 자리를 바꿔가며 만들 수 있습니다.

 

 

조합

package lecture;


import java.util.Arrays;


public class Test {
	static int N = 5;
	static int R = 3;
	static int[] src = { 1, 2, 3, 4, 5 };
	static int[] tgt = { 0, 0, 1, 1, 1 };
	static int cnt;


	public static void main(String[] args) throws Exception {
		// nCr = 5C3 = 10 가지

		Arrays.sort(tgt);
		System.out.println("tgt[]: " + Arrays.toString(tgt));

		while (true) {
			for (int i = 0; i < N; i++) {
				if (tgt[i] == 0) continue;
				System.out.print(src[i] + " ");
			}

			System.out.println();

			cnt++;
			if (!np()) break;
		}

		System.out.println("총 가짓 수 : " + cnt);

	} // end main


	private static boolean np() {
		int i = N - 1;
		int j = i;
		int k = i;

		while (i > 0 && tgt[i - 1] >= tgt[i]) i--;

		if (i == 0) return false;

		while (tgt[i - 1] >= tgt[j]) j--;
		swap(tgt, i - 1, j);

		while (i < k) swap(tgt, i++, k--);

		return true;

	} // end np


	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	} // end swap
}

출력

next permutation 으로 조합을 만들고자 한다면 tgt 는 0 과 1 로 이루어진 배열이어야 합니다.

여기서 1이면 출력이 되는 것이고, 0 이면 무시가 되는 것입니다.

 

 

 

 

 

 

 

 

 

# next permutation java # next permutation 조합 # next permutation 순열

---