순열

순열

1.순열

 순서를 정해서 나열한다. 

 서로 다른 n개중 r개를 선택하는 경우의 수(순서를 보장하고, 중복을 허용하지 않는다.)

https://mathbang.net/546

2.중복 순열

서로 다른 n개중 r개를 선택하는 경우의 수(순서를 보장하고, 중복을 허용한다.)

3.원 순열

 원모양 테이블에 n개의 원소를 나열 => 회전하면서 다른 순서도 같은순서로 변함 

 원위에 순열을 올리는게 아니라 회전하는 순열이다.  이때 회전으로 겹치지 않는 수도 고려해줘야 한다. 

 

 

ex) 4가지 서로다른 숫자중 3자리숫자를 만들수 있는 경우의 수(중복 x)

swap을 이용한 구현

import java.util.ArrayList;

//서로 다른 4가지 수를 이용하여 세자리 자연수를 만드는 방법
public class Practice {

    void permutation(int[] arr, int depth, int n, int r) {

        if(depth == r){ // 자리수가 r자리수가 되면
            for(int i =0; i < r; i++){ // 배열을 3번째까지 출력시켜준다.
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }


        for(int i = depth; i < n; i++){ // 0번째 자리부터 시작한다.
            System.out.println("----swap1 시작----");
            swap(arr, depth, i);// {1,2,3,4},자리수 1번쨰, 0번
            System.out.println("i : " + i + "  depth : " + depth);

            System.out.println("---- permutation ----");
            permutation(arr, depth + 1, n, r);


            System.out.println("----swap2 시작----");
            swap(arr, depth, i);
            System.out.println("i : " + i + "  depth : " + depth);

        }


    }

    void swap(int[] arr, int depth, int index){ // depth와 index의 자리를 바꿈
        int tmp = arr[depth]; //
        arr[depth] = arr[index];
        arr[index] = tmp;
    }




    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};

        Practice p = new Practice();
        p.permutation(arr, 0, 4, 3);
    }


}

 

visited를 사용한 구현

.

import java.util.Arrays;

public class Practice {
    void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
        if(depth == r){
            System.out.println(Arrays.toString(out));
            return;
        }
        
        for(int i=0; i<n; i++){
            if(visited[i] != true){ // 만약 방문하지 않은 곳이면 진입
                visited[i] = true; // 방문 체크
                out[depth] = arr[i]; //자리 채워줌
                permutation(arr, depth+1,n,r,visited,out); // 재귀호출
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
//      Test code
        int n = 4;
        int r = 3;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];
        int[] out = new int[4];

        Practice p = new Practice();
        p.permutation(arr, 0, n, r, visited, out);
    }
}

위의 표는 한글로 작성했다. 다시 되돌아 가는 과정을 머리속으로만 찾기는 힘들어서 Stack 항목을 만들어서 재귀함수의 이동을 확인했다.