-
[알고리즘 정리] 순열, next_permutation 구현Development/Algorithm 2020. 4. 29. 01:39
다룰 내용
- 순열이란 무엇인가?
- 순열 구현
- next_permutation이란 무엇인가?
- next_permutation 구현
순열이란 무엇인가?
순서 있게 수들을 나열하는 것으로, 원소의 순서가 의미있다면 순열입니다.
서로 다른 N개의 수 중에 R개를 선택하여 나열(nPr)로 표현할 수 있고
경우의 수를 구하면 nPr = n * n - 1 * n - 2 ~~ n - r + 1 이렇게 구할 수 있습니다.
순열을 구현하는 방법
- 각 자리에서 앞 쪽에 선택된 수를 배제합니다. (앞쪽에서 선택된 수를 알기 위해 boolean 배열 사용)
- 현재 자리에서 선택 가능한 수를 선택합니다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Permutation { public static int N, R; public static int origin[], number[]; public static boolean isSelected[]; public static void main(String arg[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input[] = br.readLine().split(" "); N = Integer.parseInt(input[0]); R = Integer.parseInt(input[1]); origin = new int[N]; isSelected = new boolean[N]; number = new int[R]; String input2[] = br.readLine().split(" "); for(int i = 0; i < N; i++){ origin[i] = Integer.parseInt(input2[i]); } permutation(0); } private static void permutation(int idx){ if(idx == R){ System.out.println(Arrays.toString(number)); return; } // 해당 자리에 뽑을 가능한 모든 수에 대해 시도 for(int i = 0; i < N; i++){ if(isSelected[i]) continue; number[idx] = origin[i]; isSelected[i] = true; permutation(idx + 1); // 다음 자리의 순열 뽑기 isSelected[i] = false; } } }
중복 순열이란 무엇인가?
서로 다른 N개의 수 중에 중복하여 R개를 선택하여 나열
n파이R = n^r 로 표현할 수 있습니다.
next_permutation이란 무엇인가?
현재 순열의 상태에서 크기순으로(사전순) 다음에 올 수 있는 순열을 생성해주는 역할을 합니다.
c++의 경우 라이브러리가 있으나 java의 경우에는 없기 때문에 암기가 어느정도 필요할 것이라고 생각합니다
예를 들어 1, 4, 5, 6라는 수가 있을 때
1 4 5 6 -> 1 4 6 5 -> 1 5 4 6 -> 1 5 6 4 ~ 식으로 순열을 만들어주는 역할을 수행하는 메소드입니다.
next_permutation 동작 방식
- 가장 작은 순열부터 시작해야합니다. (그래야 모든 순열을 다 생성할 수 있기 때문입니다.)
- 하나의 순열을 처리하고 다음 순열을 받아서 데이터를 처리하는 식으로 쓰기 때문에 do - while 형태로 구현합니다.
- 메소드 호출로 받은 순열을 사용한 후 next_permutation()을 호출하여 다음 순열을 받습니다.
- 이때 next_permutation의 리턴 값은 boolean 값으로 다음 순열을 만들 수 있는지 없는지를 반환해주는 형태로 구현합니다.
- next_permutation
- 뒤쪽부터 탐색하며 꼭대기를 찾아야합니다.
- i - 1 위치와 교환할 큰 값을 찾습니다.
- 그리고 i - 1과 j의 값을 교환합니다.
- 꼭대기부터 뒤까지 오름차순으로 정렬합니다.
next_permutation 구현 방법
- 뒤쪽부터 탐색하며 꼭대기를 찾아야합니다. (뒤에서 시작했을 때 오름차순이 끝나는 지점이 꼭대기(i)입니다.)
- i - 1 위치와 교환할 큰 값을 찾습니다.(꼭대기(i) 바로 앞자리와 교환할 큰 값을 찾아야합니다.)
- i - 1과 j의 값을 교환(교환 후 여전히 꼭대기부터 맨 뒤 원소까지 내림차순으로 되어있습니다.)
- 꼭대기부터 뒤까지 오름차순으로 정렬(따로 정렬 알고리즘을 사용할 필요는 없습니다.)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class NextPermutation { public static int N, origin[]; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); String input[] = br.readLine().split(" "); origin = new int[N]; for(int i = 0 ; i < N; i++) { origin[i] = Integer.parseInt(input[i]); } Arrays.sort(origin); do { System.out.println(Arrays.toString(origin)); } while(next_permutation()); } private static boolean next_permutation() { int i = N - 1; while(i > 0 && origin[i - 1] >= origin[i]) --i; if(i == 0) return false; int j = N - 1; while(origin[i - 1] >= origin[j]) --j; int tmp = origin[i - 1]; origin[i - 1] = origin[j]; origin[j] = tmp; int k = N - 1; while(i < k) { tmp = origin[i]; origin[i] = origin[k]; origin[k] = tmp; ++i; --k; } return true; } }
next_permutation은 현재 순열보다 큰 순열을 만들어주기 때문에 중복되는 수의 입력이 들어와도 중복이 제거됩니다.
1 1 3이 들어왔을 때 6가지의 경우가 나오지만 next_permutation은 3가지 경우만 만들어집니다.
'Development > Algorithm' 카테고리의 다른 글
[알고리즘 정리] Dijkstra(다익스트라) (0) 2020.05.03 [알고리즘 정리] Kruskal & Prim(크루스칼과 프림) (0) 2020.05.03 [알고리즘 정리] 조합, 부분 집합 구현 (0) 2020.05.03 [알고리즘 정리] Union-Find(유니온 파인드) (0) 2020.05.03 [알고리즘 정리] 재귀 (0) 2020.04.08