조합 알고리즘( N개에서 C개 뽑기 ) - JAVA 자바

코드 상에서 N은 5, C는 3이다. 순열과 조합에서 조합은 순서가 없는 것이 특징이다.

(-> {1, 2, 3} = {2, 1, 3} = {3, 1, 2} 다 같은것으로 취급 )

 

public class example {
    static int[] a = {1, 2, 3, 4, 5};
    static boolean[] a_b = {false, false, false, false, false};

    public static void main(String args[]) {
        combination(0, 1);

    }
    public static void print_arr() {
        for(int i =0; i< a_b.length; i++) {
            if(a_b[i])
                System.out.print(""+a[i]+" ");
        }
        System.out.println();
    }

    //count(= 몇 개를 뽑을지). 그리고 index(= 숫자 뽑는데 쓰이는 Iterator 역할).
    public static  void combination(int index, int count)
    {
    	//4번째 재귀에 이 구문이 실행된다. 출력 후 재귀탈출. (뽑는건 세번째에서 끝)
        if(count==4) {
            print_arr();
            return ;
        }
        else {
            for(int z = index; z < a.length; z++) {
                if(a_b[z]) // 선택된 숫자는 무시
                    continue;
                else { //false일 경우
                    a_b[z] = true; // 선택되지 않은 숫자일 경우 선택하는 것.
                    combination(z+1, count+1); // 마지막으로 선택한 숫자 이후부터 다시 선택검사 시키도록.(뒤는 돌아보지 않음)
                    a_b[z] = false; // 해당 숫자에 대한 모든 조합이 끝나면 false, 그리고 다음 숫자로 이동시키는 것.
                }
            }
        }
    }
}

 

 

1 2 3 4 5 가 있을 때.

count (= 뽑는 수 ) 가 3일때 까지 숫자를 뽑고, 4가 되면 재귀를 탈출하도록 한다. ( 뽑는건 세번에서 끝나고, 뽑고 난 후 호출되는 4번째에  count==4에 걸려 재귀를 탈출하게 된다.)

처음엔 1을 뽑은 함수 안에 2를 뽑는 함수가 실행되고 그리고 그 안에 3을 뽑는 함수가 실행된다.

3을 뽑은 함수가 count 가 4인 재귀함수를 다시 호출하면, 여지까지 뽑았던 숫자들을 출력하고 재귀함수를 탈출시킨다.

그럼 3을뽑은 함수의 a_b[z] = false로 되고, 다시 for문을 돌면서 4를 뽑게 되고 다시 count가 4인 재귀함수를 다시 호출하여 재귀를 탈출하고 이렇게 5까지 뽑은 뒤에는 for문이 종료되어 재귀가 하나 사라지게 되고, 세번째 재귀가 없는 채로 두번째 재귀(2를 뽑았던 함수) a_b[z]=false처리하면서 그 다음인 3을 뽑게 된다( 1 3 상태가 되는 것). 그리고 이 3을 뽑은 함수가 다시 4를 뽑는 함수를 실행하게 되면서 이렇게 3개의 재귀가 유지되면서 숫자를 뽑고, 4번째 재귀가 되거나(세개 뽑기 완료) 포문이 종료될 때(현재 포문이 출력하려는 x번째 자리에서 뽑을 수 있는 경우 모두 뽑음) 재귀를 벗겨가며 실행해나가게 된다.

 

한 함수에서 한 자리씩 뽑아준다고 생각하면 된다. 그리고 각 함수에서 for문을 통해 1~5까지의 경우를 모두 소화하고 난 뒤에는 그 재귀함수가 소멸되는것. (4번째 재귀는 그냥 출력만하고 소멸)

 

1 재귀에서 1~5 경우에 따라 2재귀 호출

2 재귀에서 1~5 경우에 따라 3재귀 호출

3 재귀에서 1~5 경우에 따라 4재귀 호출 하며 4 재귀(count==4)는 배열 출력 후 바로 소멸(배열 출력 역할).