Next permutation

• 현 순열에 대해 다음 순열 생성(사전 순서 기준)

algorithm

1. 꼭대기 위치 $i$ 찾기
   여기서 꼭대기는 뒤에서부터 순차적으로 탐색할 때 오름차순에서 내림차순으로 전환되는 첫 위치를 말한다.
2. 꼭대기 직전 위치의 수에 놓을 한 단계 큰 수를 뒤에서 찾기
   즉 꼭대기 위치 $i$에 대해 $i - 1$에 놓을 $a[i]$보다 작으면서 가장 큰 수를 $i + 1$ ~ $n$에서 찾는다.
3. 앞에서 찾은 수와 $a[i-1]$을 swap한다.
4. 꼭대기부터 맨 뒤까지 오름차순 정렬한다.
   
   

더 엄밀하게는 다음과 같다.

1. 배열 오름차순 정렬
   [1, 2, 3, 4]
2. 현재위치 $i$의 뒤쪽부터 탐색하며 교환 위치($i - 1$)를 찾는다.
   [1, 2, 3, 4]
3. 뒤쪽부터 탐색하며 교환 위치($i - 1$)과 교환할 큰 값의 위치 $j$를 찾는다.
   [1, 2, 3, 4]
4. 두 위치의 값을 swap한다.
   [1, 2, 4, 3]
5. $i$부터 맨 뒤까지 오름차순 정렬한다.
6. 가장 큰 내림차순 순열을 만들 때까지 2 ~ 4를 반복한다.
   
   

$cf.$

배열을 오름차순 정렬해 가장 작은 순열을 한 번 처리한다.

단계 5가 필요한 이유

[1, 2, 4, 3]에 대해 다시 2~4를 수행하면 다음과 같다(현재 i = 2).

• [1, 2, 4, 3]
• [1, 2, 4, 3]
• [1, 3, 4, 2]
  여기까지만 하면 correctness가 보장되지 않는다. [1, 2, 4, 3]의 next permutation은 [1, 3, 2, 4]다.
  단계 5를 거치면 [1, 3, 2, 4]가 된다.
  
  

그냥 순열이랑 뭐가 다른가요

• 이게 더 빠름
• 근데 $_{n}\text{P}_{n}$밖에 못 함
• 재귀는 $_{n}\text{P}_{n}$, $_{n}\text{P}_{r}$, $_n \Pi _r$ 다 가능
• 그래도 하면 좋은 이유는 이걸로 순열, 조합 다 되기 때문
• 일단 빠르니까 $_{n}\text{P}_{n}$이 필요할 때 쓰면 더 더 좋을 것
  
  

구현

import java.util.*;

public class NPTest {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] input = new int[n];
		for(int i = 0; i < n; input[i++] = sc.nextInt());
		Arrays.sort(input);
		
		do {
			System.out.println(Arrays.toString(input));
		} while(np(input));
		
		sc.close();
	}
	
	private static boolean np(int[] p) { //p: 다음 순열을 뽑아낼 배열
		/** 1.
		 * 꼭대기 위치 <code>i</code>를 뒤쪽에서부터 찾는다.
		 */
		int n = p.length;
		int i = n - 1;
		while(i > 0 && p[i - 1] >= p[i]) --i;
		
		if(i == 0) {
			//현재 순열은 만들 수 있는 가장 큰 순열임을 의미함
			//즉 다음 순열이 없음
			return false;
		}
		
		/**
		 * 2.
		 * <code>i - 1</code>에 교환할 한 단계 큰 수의 위치
		 * <code>j</code>를 뒤쪽부터 찾음
		 */
		int j = n - 1;
		while(p[i - 1] >= p[j]) --j;
			
		/**
		 * 3.
		 * <code>i - 1</code>위치의 수와 한 단계 큰 수 swap
		 */
		swap(p, i - 1, j);
		
		/*
		 * 4.
		 * 꼭대기 자리부터 맨 뒤까지의 수를 오름차순 정렬
		 */
		int k = n - 1;
		while(i < k) swap(p, i++, k--);
		
		/*
		 * 5.
		 * 다 끝났음
		 * 배열 자체를 수정했으므로 굳이 새로 배열을 만들 필요는 없음
		 */
		return true;
	}
	
	private static void swap(int[] p, int a, int b) {
		p[a] ^= p[b];
		p[b] ^= p[a];
		p[a] ^= p[b];
	}

}

조합

import java.util.*;

public class CombinationNPTest {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();
		int[] input = new int[n];
		for(int i = 0; i < n; input[i++] = sc.nextInt());
		Arrays.sort(input);

		int[] p = new int[n];
		int count = 0;
		while(++count <= r) p[n - count] = 1; 

		do {
			for(int i = 0; i < n; ++i) {
				if(p[i] == 0) continue;
				System.out.print(input[i] + "\t");
			}
			System.out.println();
			//System.out.println(Arrays.toString(input));
		} while(np(p));

		sc.close();
	}

	private static boolean np(int[] p) { //p: 다음 순열을 뽑아낼 배열
		int n = p.length;
		int i = n - 1;
		while(i > 0 && p[i - 1] >= p[i]) --i;

		if(i == 0) { return false; }

		int j = n - 1;
		while(p[i - 1] >= p[j]) --j;

		swap(p, i - 1, j);

		int k = n - 1;
		while(i < k) swap(p, i++, k--);

		return true;
	}
	
	private static void swap(int[] p, int a, int b) {
		if(p[a] == p[b]) return;
		
		p[a] ^= p[b];
		p[b] ^= p[a];
		p[a] ^= p[b];
	}

}