C++, python과 같은 언어에서는 nextPermutation()과 같은 함수가 있어서 순열에 대한 처리가 굉장히 편하다. 하지만, Java에는 없기 때문에 직접 만들고 그 원리를 이해하고자 한다.
다음순열
다음 순열을 구하는 알고리즘은 다음과 같다.
1. 주어진 순열을 탐색하며 N[i] < N[i + 1]인 가장 마지막 i를 찾는다.
- i를 찾지못하면 주어진 순열이 마지막 순열이다.
2. 주어진 순열의 마지막부터 앞쪽으로 탐색하여 N[j] > N[i]인 첫 번째 j를 찾는다.
3. 주어진 순열에서 ì 와 j의 위치를 바꾼다(swap(i, j)).
4. 주어진 순열에서 i + 1 부터 끝까지를 뒤집는다(reverse).
// 다음 순열 함수은 O(n)의 시간복잡도를 갖는다.
private static int[] nextPermutation(int[] permutation) {
// 1차원 배열은 clone()으로 deep copy 가능
int[] next = permutation.clone();
int first = -1, second = -1;
// 주어진 순열을 탐색하며 N[i] < N[i + 1]인 가장 마지막 i를 찾는다.
for(int i = 0 ; i < next.length - 1 ; ++i) {
if(next[i] < next[i + 1]) {
first = i;
}
}
// i를 찾지 못하면 현재 순열이 마지막 순열이다.
if(first == -1) return null;
// 주어진 순열의 마지막부터 역으로 탐색하며 N[j] > N[i]인 첫 번째 j를 찾는다.
for(int j = next.length - 1 ; j >= 0 ; --j) {
if(next[j] > next[first]) {
second = j;
break;
}
}
// i, j의 위치를 바꾼다.
swap(next, first, second);
// i + 1 부터 끝까지를 뒤집는다.
int left = first + 1;
int right = next.length - 1;
while(left < right) {
swap(next, left, right);
left++;
right--;
}
return next;
}이전순열
이전 순열을 구하는 알고리즘은 다음 순열 알고리즘에서 부등호만 바꾸면 된다.
// 다음 순열 함수은 O(n)의 시간복잡도를 갖는다.
private static int[] beforePermutation(int[] permutation) {
// 1차원 배열은 clone()으로 deep copy 가능
int[] before = permutation.clone();
int first = -1, second = -1;
// 주어진 순열을 탐색하며 N[i] > N[i + 1]인 가장 마지막 i를 찾는다.
for(int i = 0 ; i < before.length - 1 ; ++i) {
if(before[i] > before[i + 1]) {
first = i;
}
}
// i를 찾지 못하면 현재 순열이 첫 번째 순열이다.
if(first == -1) return null;
// 주어진 순열의 마지막부터 역으로 탐색하며 N[j] < N[i]인 가장 첫 번째 j를 찾는다.
for(int j = before.length - 1 ; j >= 0 ; --j) {
if(before[j] < before[first]) {
second = j;
break;
}
}
// i, j의 위치를 바꾼다.
swap(before, first, second);
// i + 1 부터 끝까지를 뒤집는다.
int left = first + 1;
int right = before.length - 1;
while(left < right) {
swap(before, left, right);
left++;
right--;
}
return before;
}모든순열
모든 순열은 위에서 만든 nextPermutation() 함수를 이용하는 방법과 재귀를 이용하는 방법이 있다.
nextPermutation()을 이용한 방법
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
for(int i = 0 ; i < N ; ++i) {
arr[i] = i + 1;
}
print(arr);
while((arr = nextPermutation(arr)) != null) {
print(arr);
}
}
private static int[] nextPermutation(int[] arr) {
int[] next = arr.clone();
int first = -1, second = -1;
for(int i = 0 ; i < next.length - 1 ; ++i) {
if(next[i] < next[i + 1]) {
first = i;
}
}
if(first == -1) return null;
for(int j = next.length - 1 ; j >= 0 ; --j) {
if(next[j] > next[first]) {
second = j;
break;
}
}
swap(next, first, second);
int left = first + 1;
int right = next.length - 1;
while(left < right) {
swap(next, left, right);
left++;
right--;
}
return next;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void print(int[] arr) {
for(int i = 0 ; i < arr.length ; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
재귀함수를 이용하는 방법
import java.util.Scanner;
public class Main {
static int N;
static boolean[] selected;
static int[] numbers;
private static void permutation(int index) {
if(index == N) {
for(int num : numbers) {
System.out.print(num + " ");
}
System.out.println();
return;
}
for(int i = 1 ; i <= N ; i++) {
if(!selected[i]) {
numbers[index] = i;
selected[i] = true;
permutation(index + 1);
selected[i] = false;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
selected = new boolean[N + 1];
numbers = new int[N];
permutation(0);
}
}
문제
그냥 개발자