순열 & 조합

Java로 순열과 조합을 어떻게 사용할까?

 

 

Python은 순열과 조합을 구하는 함수가 내장되어 있습니다.

Java는 그렇지 않기에 이번글은 Java로 순열과 조합을 구현한 코드에대해 알아보겠습니다.

 

Java로 순열을 어떻게 구현할 수 있을까요?

 

순열

 

순열은 순서가 중요한 경우의 수를 구하는 방법입니다.

 

[A, B, C]에서 2개를 뽑아서 나열하는 경우, [A,B], [A,C], [B,A], [B,C], [C,A], [C,B]가 됩니다. 이는 똑같은 두 글자를 뽑아도, 순서가 다르면 다른 경우로 취급합니다.

 

Java로 구현한 코드는 다음과 같습니다.

public class Permutation {

    private static String[] array = {"A","B","C"};

    public static void main(String[] args) {
        permutation(new String[2], new boolean[3], 0);
    }

    public static void permutation(String[] result, boolean[] visited, int depth) {
        if(depth == 2) {
            System.out.println(Arrays.toString(result));
            return;
        }

        for(int i = 0; i < array.length; i++) {
            if(!visited[i]) {
                result[depth] = array[i];
                visited[i] = true;
                permutation(result, visited, depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

출력한 결과는 다음과 같습니다.

 

조합

순서가 중요하지 않은 경우의 수를 구하는 방법입니다.

[A,B,C]에서 2개를 뽑아 나열하는 경우, [A,B], [A,C], [B,C]가 됩니다. 이는 AB와 BA는 같은 경우로 취급하고, 순서는 쓰지 않습니다.

 

Java로 구현한 코드는 다음과 같습니다.

public class Combination {
    private static String[] array = {"A","B","C"};

    public static void main(String[] args) {
        combination(0, new String[2], 0);
    }

    public static void combination(int start, String[] result, int depth) {
        if(depth == 2) {
            System.out.println(Arrays.toString(result));
            return;
        }

        for(int i = start; i < array.length; i++) {
            result[depth] = array[i];
            combination(i + 1, result, depth + 1);
        }
    }
}

 

출력한 결과는 다음과 같습니다.

 

 

정리

• 순열은 visited 배열이 필요합니다. 순서를 다 다르게 세야 하기 때문입니다.
• 순열은 for(0부터 끝까지) 탐색합니다.
• 조합은 start 변수를 사용합니다. 앞에서 뽑은 다음부터만 뽑으면 끝나기 때문입니다.
• 조합은 for (start부터 끝까지) 탐색합니다.