java - 순열(조합과의 비교)

일전에, 재귀함수를 다루면서 조합을 다룬바 있다.(참고 : https://severalpg.tistory.com/20)

 

조합과 순열이 무엇인지에 대한 개요는 생략하도록하겠다. 바로 재귀함수를 통해 구현된 코드를 실행시키고 결과값을 봐보도록 하자.

 

조합

import java.util.*;
public class Combination {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        for(int i =1; i<=arr.length; i++){
            recur(arr, new int[i], 0, 0);
        }
    }
    static void recur(int[] arr, int[] new_arr, int start, int num){
        if(num == new_arr.length){
            System.out.println(Arrays.toString(new_arr));
            return;
        }
        for(int i=start; i<arr.length; i++){
            new_arr[num] = arr[i];
            recur(arr, new_arr, i+1, num+1);
        }
    }
}

 

순열

import java.util.Arrays;
public class Permutation {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30};
        for(int i =1; i<=arr.length; i++){
            recur(arr, new int[i], new int[arr.length], 0);
        }
    }
    static void recur(int[] arr, int[] new_arr, int[] checked, int num){
        if(num == new_arr.length){
            System.out.println(Arrays.toString(new_arr));
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(checked[i] != 1){
                new_arr[num] = arr[i];
                checked[i] = 1;
                recur(arr, new_arr, checked, num+1);
                checked[i] = 0;
            }
        }
    }

}

 

조합과 순열을 만듬에 있어 배열(위 코드의 new_arr)을 쓰는 이유는 List같은것들에 비해 배열에서는 값을 덮어쓰기를 통해 간단하게 재귀함수를 활용하여 새로운 배열을 만들어낼 수 있기 때문이다. 재귀함수를 호출할때만 num값을 ++ 시킴으로서 배열의 index값을 num을 통해 조절할 수 있다.

 

조합은 순열과 비교하여 차이점은, int i의 start 값을 재귀함수를 호출할때마다 1씩 늘려간다는 점이다. 예를 들어 {10,20,30}과 {30,20,10}은 조합에서는 같은 것이기에 10이후의 값인 20, 30 값만 가져오면 되므로 starting지점을 늘려가는 방식으로 구현을 한다.

 

순열은 조합과 비교했을때, 재귀함수가 반복적으로 호출되더라도 항상 starting index값이 0이다. 이때에 발생할 수 있는 문제점은 계속해서 한 index값만을 가져올수가 있다는 것이다. 예를 들어 {10,10,10} 의 결과값을 return할수가 있게 된다.

 

이를 방지하기 위해, 한번 입력된 값은 다시 배열에 담지 않도록 검증배열(위 코드의 checked)을 하나 만든다. 이때 주의할점은 이 checked배열의 길이는 새로 만들 순열의 new_arr이 아닌, 원본배열(위의 arr)의 길이와 같아야 한다는 점이다. 원본배열의 특정 index의 값들이 새로운 순열배열을 만드는 데 사용이 되었는지를 체크하는 것이기 때문이다.

 

검증배열을 활용할때에, 이해하기 어려운 부분은 checked[i]를 1(또는 true)로 바꾼뒤에 한번의 재귀함수가 끝나고 나면 다시 0(또는 false)로 바꾼다는 점이다. 이는 재귀함수를 머릿속에서 시뮬레이션을 잘해야 이해가능한 부분이다. 잘 생각해보자.

 

예를 들어, {10,20 ...} 과 같이 20까지 세팅한 뒤에 재귀함수를 호출해서 그 뒤에 값들을 채워나갈 것이다. 그런데, 다시 20 뒤의 재귀문이 끝나고 다시 for문으로 돌아오게 되면 20자리에는 이제 30이 세팅될 것인데, 그 이후의 재귀함수의 식들에서 20은 사용가능한 것이어야 한다. 그래야지 {10,30,20 ...}이 될수가 있기 때문이다.

 

즉, 1번의 for문이 반복되고나면 다시 시작되는 for문의 재귀함수 내에서 20은 사용가능한 값이 되어야 하기 때문에, checked[i]값을 다시 되돌려 놓는 것이다. 어차피 for문은 순차적으로 index를 조회하므로, {10,20,20...}이 되지는 않는다.

 

내가 생각하기에 재귀함수와 순열/조합을 이해하는 좋은 방법은 책상에 앉아서 코드를 뚫어져라 쳐다보기 보다는, 일단 코드를 전체적으로 암기한 뒤에 산책이라도 하면서 코드들을 떠올리며 재귀함수의 흐름을 하나씩 시뮬레이션 해보는 것이라 생각한다. 재귀함수는 처음에는 직관적으로 머릿속에서 그려지지 않기 때문에, 여러번 반복적인 사고를 통해서야 온전한 이해가 가능할 것이라 생각한다.