[JAVA] JAVA에서 순열 (Permutation)

참고 사이트

순열 Permutation (Java)

순열

n개의 원소 중에서 r개를 순서대로 뽑는 경우의 수

 

Swap을 이용한 순열

배열의 첫번째 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap한다.

depth 기준 인덱스로 이보다 인덱스가 작으면 고정, 큰 값들만으로 swap

순열의 순서가 보장되지 않는다.

import java.util.*;


public class Main {
    // r은 몇개 꺼낼지
    public static void permutation(int[] arr, int depth, int r) {
        if (depth == r) {
            //순열 끝 출력
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = depth; i < arr.length; i++) {
            swap(arr, depth, i); // 바꾸고
            permutation(arr, depth+1, r);
            swap(arr, depth, i); // 자기 자신 복원
        }
        
    }

    public static void swap (int[] arr, int depth, int i) {
        int tmp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = tmp;
    }

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

    }
}

 

Visited 배열을 이용한 순열

사전식으로 순열을 구현할 수 있다. (원하는 순서대로)

아웃풋을 하나씩 늘려가면서 (depth가 인덱스 역할) 하나씩 뽑아서 저장한다는 느낌.

import java.util.*;


public class Main {

    public static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth+1, r);
                // output[depth] = 0;
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        
        int[] arr = {1,2,3};
        int r = 3;
        int[] output = new int[r];
        boolean[] visited = new boolean[arr.length];
        permutation(arr, output, visited, 0, r);

    }
}

 

추가 참고 사이트

순열(Permutation) 알고리즘 Java로 구현하기