[순열] Swap을 이용한 순열

배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한 번씩 swap
depth를 기준 인덱스로 하여 depth보다 인덱스가 작은 값들을
그대로 고정하고 depth보다 인덱스가 큰 값들만 가지고 다시 swap

순서가 보장되지 않음 마지막 321,312 부분

public class Permutation {
    public static void main(String[] args) {
        int n = 3;
        int[] arr = {1, 2, 3};
        int[] output = new int[n];
       //boolean[] visited = new boolean[n];
       // visited를 이용한 순열에서 설명예정
       // perm(arr, output, visited, 0, n, 3);
       // System.out.println();
        permutation(arr, 0, n, 3);
    }

// 순서 없이 n 개중에서 r 개를 뽑는 경우
// 사용 예시: permutation(arr, 0, n, 3);
static void permutation(int[] arr, int depth, int n, int r) {
    if (depth == r) {
        print(arr, r);// 3개 뽑을 때 출력
        return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i); // 여기서 실질적으로 바뀌어짐
				
        permutation(arr, depth + 1, n, r); //재귀 함수 호출
				
        swap(arr, depth, i); // 바꾼 것을 원 위치
    }
}

	 
static void swap(int[] arr, int depth, int i) { // 위치 바꾸는 메소드
    int temp = arr[depth]; // 원래 있던 숫자 임시 변수에 저장
    arr[depth] = arr[i];   // depth가 1이고 i가 2일때 처음 바뀜
    arr[i] = temp;         // 자리를 바꿈 
    
}

static void print(int[] arr, int r) { // 출력 메소드
        for (int i = 0; i < r; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}
//결과
//그림과 같음
1 2 3 // 그대로 출력
1 3 2 // 끝 자리 뒤바꿔서 출력
2 1 3 // 첫 자리와 두번째 자리 바꾸고 출력
2 3 1 // 끝 자리 뒤바꿔서 출력
3 2 1 // 첫 자리와 두번째 자리 바꾸고 출력
3 1 2 // 끝 자리 뒤바꿔서 출력

 

출처 : https://bcp0109.tistory.com/14

순열 Permutation (Java)