순열(Permutation), 조합(Combination)

순열과 조합에 대해 알아봅시다.

 

1. 순열 (Permutation)

서로 다른 N개의 원소에서 R개를 중복없이 골라 순서에 상관있게 나열하는 것입니다.

1, 2, 3 과 1, 3, 2는 서로 다른 것으로 처리하는 것입니다.

 

먼저 순열을 구현하는 방법을 알아봅시다.

4개의 숫자중에서 3개를 선택하는 문제입니다.

4P3 = 4 x 3 x 2 = 24개의 결과를 얻을 수 있습니다.

 

코드로 살펴보도록 하겠습니다.

 

구현 방법은 dfs와 동일합니다.

dfs를 배웠으니 동작 원리가 대충 이해가 가시나요?

재귀 함수를 사용하였기 때문에 아래와 같은 방법으로 돌아가는 것을 예상할 수 있습니다.

 

1 -> 2 -> 3 (return) 

        2 -> 4 (return)

        2 (return)

   -> 3

1 -> 2 -> 3
       -> 4
     3 -> 2
       -> 4
     4 -> 2
       -> 3
2 -> 1 -> 3
     .
     . 
     .
3 -> 
     .
     .
     .
4 ->

private static void permutation(Stack<Integer> stack, int[] arr) {
        if (stack.size() == 3) {
            System.out.println(stack);
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visit[i]) {
                stack.add(arr[i]);
                visit[i] = true;
                permutation(stack, arr);
                visit[i] = false;
                stack.pop();
            }
        }
    }

import java.util.Stack;

public class Permutation {
    private static boolean[] visit;

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        visit = new boolean[arr.length];
        Stack<Integer> stack = new Stack<>();
        permutation(stack, arr);
    }

    private static void permutation(Stack<Integer> stack, int[] arr) {
        if (stack.size() == 3) {
            System.out.println(stack);
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visit[i]) {
                stack.add(arr[i]);
                visit[i] = true;
                permutation(stack, arr);
                visit[i] = false;
                stack.pop();
            }
        }
    }
}

 

조합 (Combination)

 

조합이랑 n개의 값 중에서 r개의 숫자를 순서에 무관하게 나열하는 방법입니다.

구현 방법은 permutation과 거의 유사합니다.

변경해야 할 부분은 for loop의 시작점과 재귀함수에 들어가는 index 부분입니다.

 

import java.util.Stack;

public class Combination {
    private static boolean[] visit;

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        visit = new boolean[arr.length];
        Stack<Integer> stack = new Stack<>();
        combination(0, stack, arr);
    }

    private static void combination(int index, Stack<Integer> stack, int[] arr) {
        if (stack.size() == 3) {
            System.out.println(stack);
            return;
        }

        for (int i = index; i < arr.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                stack.add(arr[i]);
                combination(i + 1, stack, arr);
                stack.pop();
                visit[i] = false;
            }
        }
    }
}

 

2가지 부분만 주의해서 수정하면 permutation 코드를 combination 코드로 변경하여 사용할 수 있습니다.