Permutation(순열)

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);
}