순열 (PERMUTATION) - 사전순

순열 (PERMUTATION) - 사전순

이전 글 : 순열 (PERMUTATION)  http://stack07142.tistory.com/24

순열을 사전순으로 만들려면 어떻게 해야 할까

[1, 2, 3, 4] 순열이 있을 때,

---------------------------------------------------------

[1, 2, 3, 4]

[1,     2, 3, 4]

[2,     1, 3, 4]

[3,     1, 2, 4]

[4,     1, 2, 3]

---------------------------------------------------------

[1,     2, 3, 4]

[1,     2,     3, 4]

[1,     3,     2, 4]

[1,     4,     2, 3]

[2,     1, 3, 4]

[2,     1,     3, 4]

[2,     3,     1, 4]

[2,     4,     1, 3]

[3,     1, 2, 4]

[3,     1,     2, 4]

[3,     2,     1, 4]

[3,     4,     1, 2]

[4,     1, 2, 3]

[4,     1,     2, 3]

[4,     2,     1, 3]

[4,     3,     1, 2]

---------------------------------------------------------

[1,     2, 3, 4]

[1,     2,     3, 4]

[1,     2,     3,     4]

[1,     2,     4,     3]

[1,     3,     2, 4]

[1,     3,     2,     4]

[1,     3,     4,     2]

[1,     4,     2, 3]

[1,     4,     2,     3]

[1,     4,     3,     2]

.........반복

static void permutation_Dic(int[] arr, int depth, int n, int k) {

    if (depth == k) {

        printArr(arr);
        return;
    }

    for (int i = depth; i < n; i++) {

        rightRotate(arr, depth, i);
        permutation_Dic(arr, depth + 1, n, k);
        leftRotate(arr, depth, i);
    }
}

static void rightRotate(int[] arr, int start, int end) {

    int last = arr[end];

    for (int i = end; i > start; i--) {

        arr[i] = arr[i - 1];
    }

    arr[start] = last;
}

static void leftRotate(int[] arr, int start, int end) {

    int first = arr[start];

    for (int i = start; i < end; i++) {

        arr[i] = arr[i + 1];
    }

    arr[end] = first;
}

static void printArr(int[] arr) {

    for (int i = 0; i < N; i++) {

        System.out.print(arr[i] + " ");
    }
    System.out.println();
}