Permutation(순열)
- Algorithm
- 2021년 5월 28일
1. next_permutation
c++에는 algorithm헤더에 매개변수의 배열/iterator의 다음 순열을 적용시켜 바뀌었다면 true/false를 반환해주는 메서드가 존재해서 이를 do~while문으로 쉽게 순열문제를 해결할 수 있다.
하지만, 자바는 존재하지 않기 때문에 다음과 같이 구현할 수 있다.
public boolean next_permutation(int[] arr){
//뒤에서부터 탐색해서 내림차순이 깨지는 지점(a) 찾기
int a = arr.length-2;
while(a>=0 && arr[a] >= arr[a+1]) a--;
if(a < 0) return false; //a가 -1이라면 배열전체가 내림차순정렬된 상태로 순열탐색이 끝난다.
//뒤에서부터 탐색하면서 a보다 큰 첫번째 인덱스(b) 찾기
int b = arr.length-1;
while(arr[a] >= arr[b])b--;
//찾은 a와 b swap
swap(arr,a,b);
//a+1부터 끝까지 오름차순으로 재정렬
a += 1;
b = arr.length-1;
while(a< b){
swap(arr,a++,b--);
}
return true;
}
private void swap(int[] arr, int src, int target){
int tmp = arr[src];
arr[src] = arr[target];
arr[target] = tmp;
}
@Test
void test(){
int[] arr = new int[]{1,2,3,4};
do{
System.out.println(Arrays.toString(arr));
}while(next_permutation(arr));
}
2. swap
구현하기가 가장 쉬워 보통 알고리즘문제에 순열이 등장할때 많이쓰는 방식중 하나로 재귀함수를 이용한 백트래킹을 이용한 방법이다.
public void permutation(int[] arr, int depth, int n,int r){
if(depth == r){
System.out.println(Arrays.toString(arr));
return;
}
for(int i=depth; i < n; i++){
swap(arr,depth,i);
permutation(arr, depth+1,n,r);
swap(arr,depth,i);
}
}
private void swap(int[] arr, int src, int target){
int tmp = arr[src];
arr[src] = arr[target];
arr[target] = tmp;
}
@Test
void test(){
int[] arr = new int[]{1,2,3,4};
permutation(arr,0,4,4);
}
3. visited
swap과 구현코드는 비슷하기 때문에 구현하는 것은 쉽게 할 수 있다. 하지만 swap과 다르게 배열의 앞에서부터 값을 쌓아나가는 방식으로 List를 이용해 값을 쌓아 나갈 수도 있고 depth가 r과 같아질때가 아니더라도 조건처리하기가 훨씬 쉽다.
if(visited[i]) continue; 부분만 지워주면 중복순열(자기자신을 포함)을 구할수 있다.
public void permutation(int arr[],int tmp[],boolean[] visited,int depth, int n, int r){
if(depth == r){
System.out.println(cnt++ + " " + Arrays.toString(tmp));
return;
}
for(int i=0; i < n; i++){
if(visited[i])continue;
visited[i] = true;
tmp[depth] = arr[i];
visitedPermutation(arr,tmp,visited,depth+1,n,r);
visited[i] =false;
}
}
public void listPermutation(int arr[], List<Integer> tmp, boolean[] visited, int depth, int n, int r){
if(depth == r){
System.out.println(tmp.toString());
return;
}
for(int i=0; i < n; i++){
if(visited[i])continue;
visited[i] = true;
tmp.add(arr[i]);
listPermutation(arr,tmp,visited,depth+1,n,r);
visited[i] =false;
tmp.remove(tmp.size()-1);
}
}
public void rePermutation(int arr[],int tmp[],boolean[] visited,int depth, int n, int r){
if(depth == r){
System.out.println(Arrays.toString(tmp));
return;
}
for(int i=0; i < n; i++){
visited[i] = true;
tmp[depth] = arr[i];
visitedPermutation(arr,tmp,visited,depth+1,n,r);
visited[i] =false;
}
}
@Test
void test(){
int[] arr = new int[]{1,2,3};
int[]tmp = new int[3];
List<Integer> list = new ArrayList<>();
boolean[] visited = new boolean[3];
System.out.println("---Array---");
permutation(arr,tmp,visited,0,3,3);
System.out.println("----List---");
listPermutation(arr,list,visited,0,3,3);
System.out.println("--중복순열--");
rePermutation(arr,tmp,visited,0,3,3);
}
