Permutation

1. 다음 순열

public static int[] a = new int[n];
public static int i;

public static void nextPerm() {
	i = -1;
	for(int k=0; k<n-1; k++) {
		if(a[k]<a[k+1]) { i = k+1; }
	}

	if(i==-1) { return; }

	int j = i;
	for(int k=i; k<n; k++) {
		if(a[i-1]<a[k]) { j = k; }
	}

	swap(i-1, j);

	for(int k=0; k<(n-i)/2; k++) { swap(i+k, n-1-k); }
}

public static void swap(int n1, int n2) {
	int temp = a[n1];
	a[n1] = a[n2];
	a[n2] = temp;
}

 

2. 이전 순열

public static int[] a = new int[n];
public static int i;

public static void prevPerm() {
	i = -1;
	for(int k=0; k<n-1; k++) {
		if(a[k]>a[k+1]) { i = k+1; }
	}

	if(i==-1) { return; }

	int j = i;
	for(int k=i; k<n; k++) {
		if(a[i-1]>a[k]) { j = k; }
	}

	swap(i-1, j);

	for(int k=0; k<(n-i)/2; k++) { swap(i+k, n-1-k); }
}

public static void swap(int n1, int n2) {
	int temp = a[n1];
	a[n1] = a[n2];
	a[n2] = temp;
}

 

참고

- 『알고리즘 기초 2/2』