재귀로 세자리 자연수 만들기(permutation 순열)

1,2,3,4를 이용하여 세자리 자연수를 만드는 방법
(순서 o, 중복 x)

방법 1

[0,1,2,3]으로 되어 있는 배열을 순서를 바꿔가며 출력한다.
예를 들어
1 2 3
1 2 4
1 3 2
...
4 1 3
4 1 2

//arr이 숫자 배열, depth는 현재 자리수, n은 숫자 개수, r은 목표 자릿수
public class Practice1 {
    void permutation(int[] arr, int depth, int n, int r) {
        //현재 자리수가 목표 자리수와 같아지면 출력
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
		
        //핵심부분
        //depth와 i가 계속 바뀌기때문에 조건을 걸어두기만하면
        //그 조건에 맞춰서 모든 상황이 출력
        //i가 계속 증가하고, swap을 통해 depth와 i가 바뀌고, 또 depth도 증가해간다
        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);//위에서 바꾼 숫자를 다시 원상 복귀
        }
    }

	//각 위치의 숫자를 바꾸는 부분
    void swap(int[] arr, int depth, int idx) {
        int tmp = arr[depth];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
    }

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

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

방법 2

재귀를 통해 모든 상황을 탐색하는 건 똑같지만
조건을 visited 배열을 통해 주었다.

import java.util.Arrays;

public class Practice2 {
    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[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[4];
        int[] out = new int[3];

        Practice2 p = new Practice2();
        p.permutation(arr, 0, 4, 3, visited, out);
    }
}