경우의 수를 찾는 방법 - 순열, 조합 그리고 재귀함수

완전탐색의 경우의 수를 푸는 알고리즘에는 순열, 조합, 중복순열이 있다.

순열

서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수를 구하는 경우. 예를 들어 3개의 알파벳 A B C의 순열은 ABC / ACB / BAC / BCA / CAB / CBA 로 총 6가지이다.

기본적으로 for문을 사용하여 순열을 찾을 수 있다.

for문으로 경우의 수를 도출

let input = [ 'a', 'b', 'c' ];
let count = 0;

function permutation(arr){
    // for i : 첫번째 index에 위치
    for(let i = 0; i < arr.length; i++){
        // for j : 두번째 index에 위치
        for(let j = 0; j < arr.length; j++){
            // i 와 중복되면 안되니까 i == j 라면 스킵.
            if(i == j) continue;
            // for k : 세번째 index에 위치
            for(let k = 0; k < arr.length; k++){
                if(i == k) continue;
                if(j == k) continue;

                console.log(arr[i], arr[j], arr[k]);
                count++;
            }
        }
    }
}
permutation(input);
console.log(count);

arr[i], arr[j], arr[k]를 찍어보면 abc acb bac bca cab cba가 나오고 count는 6이 출력된다.

요소가 너무 많아지면 for문으로는 대처하는데에 한계가 있다. 그럴때 재귀함수를 주로 사용한다. 재귀함수는 자기 스스로를 호출하는 함수이다.

재귀함수로 경우의 수를 도출

재귀함수의 도출할때는 함수 속에서 자기 자신의 함수를 다시 호출하면서 로직이 반복되는데 주의할 점은 재귀함수를 멈춰야할 조건을 설정해 주어야 한다는 것이다.

아래의 예제는 재귀함수를 사용해 매개변수만 수정하면서 스스로를 다시 호출, 로직을 돌며 배열 아이템의 순서가 동일할 경우는 위치를 그대로 두고, 다를 경우에는 앞뒤의 위치를 바꿔주는 방식으로 경우의 수를 도출한 방법이다. 매개변수에는(입력값이 담긴 배열, start위치(입력값중 첫번째), 출력할 요소 개수)을 준다.

let input = [ 'a', 'b', 'c' ];
let _count = 0;
function _permutation(arr, s, r){
    // 1.재귀함수를 멈춰야할 조건
    if(s == r){
        _count++;
        console.log(arr.join(" "));
        return;
    } 
    // 2.재귀를 돌면서 변경되어야 될 부분 
    for(let i = s; i < arr.length; i++){
        [arr[s],arr[i]] = [arr[i],arr[s]]; // swap
        _permutation(arr, s + 1, r);
        [arr[s],arr[i]] = [arr[i],arr[s]]; // 원상복귀
    }
}
_permutation(input, 0, 3);
console.log(_count);

위의 예제의 for문을 보면 i의 자리에 s를 대입하고( 재귀함수를 처음 호출했을 때, i의 값이 s의 값과 같게 시작하는 이유이다. ) i는 배열 아이템의 길이까지 반복된다. 재귀함수가 호출될때 s + 1을 하면서 실행이 되고, s==r 이라면 그 전까지의 배열이 즉시 출력되고 return되어 그 전의 함수(재귀함수를 호출했던 함수)로 돌아가서 아래의 남아있던 코드가 실행된다.

과정

[_permutation]
s=0,i=0 -> [0,0]=[0,0] > [a,a]=[a,a] -> s+1하며 재귀함수 호출

[_permutation-1] 
s=1,i=1 (s의 값을 i에 대입해서 i값이 1에서 부터 시작) -> [1,1]=[1,1] > [b,b]=[b,b] -> s+1하며 재귀함수 호출

[_permutation-2]
s=2,i=2 -> 재귀함수 멈추는 조건 true -> count++하고 그전까지의 arr을 출력([a,b,c] : swap없었음)
return ( '_permutation-1'으로 돌아감 )

[_permutation-1] - 재귀함수 호출코드 아래 코드부터 실행
s=1,i=1 -> [1,1]=[1,1] > [b,b]=[b,b] -> swap하지않음 -> 그대로[a,b,c]
i++ 
s=1,i=2 -> [1,2]=[2,1] > [b,c]=[c,b] -> swap -> [a,c,b] -> s+1하며 재귀함수 호출

[_permutation-3]
s=2,i=2 -> 재귀함수 멈추는 조건 true -> [a,c,b]출력
return ('_permutation-1'로 돌아감)

[_permutation-1]
s=1,i=2 -> [1,2]=[2,1] > [c,b]=[b,c] -> swap -> [a,b,c]
i=2로 반복문 종료 (*코드가 끝나지 않은'_permutation'이 실행*)

[_permutation] - 재귀함수 호출코드 아래 코드부터 실행
s=0,i=0 -> [0,0]=[0,0] > [a,a]=[a,a] -> [a,b,c]
i++
s=0,i=1 -> [0,1]=[1,0] > [a,b]=[b,a] -> [b,a,c]
.
.
.
s=0,i=2
[0,2]=[2,0] > [a,c]=[c,a] -> [c,a,b]

---

조합

서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수를 구하는 경우. 예를 들어 1,2,3,4 4개의 숫자 카드에서 2개를 뽑는 조합은 1 2 (2 1과 같다) / 1 3 / 1 4 / 2 3 / 2 4 / 3 4로 총 6개이다.

4C2(4combination2) = nCr
nCr = n! / (n-r)! r! = 4321 / 2*2 = 6

for문으로 경우의 수를 도출

let input2 = [1, 2, 3, 4];
let count2 = 0;

function combination(arr){
    for(let i = 0; i < arr.length; i++){
      // i 이후의 값만 선택되도록 i + 1을 해주었다.
        for(let j = i + 1; j < arr.length; j++){
            count2++;
            console.log(arr[i], arr[j]);
        }
    }
}
combination(input2);
console.log(count2);

재귀함수로 경우의 수를 도출

매개변수로 아웃풋이 저장될 data와 현재위치 정보를 주는 idx가 추가되었다.

let input2 = [1, 2, 3, 4];
let count2 = 0;
let output = [];

function _combination(arr, data, s, idx, r){
    if(s == r){
        count3++;
        console.log(data);
        return;
    }
    for(let i = idx; arr.length - i >= r - s; i++){
        data[s] = arr[i];
        _combination(arr, data, s + 1, i + 1, r);
    }
}
_combination(input2, output, 0, 0, 2);
console.log(count3);

과정

[_combination](Com) s=0, idx(i)=0 -> data[0] =1; ->재귀호출
[Com-1] s=1, idx(i)=1 -> data[1] =2; ->재귀호출
[Com-2] s=2 -> s==r -> [1,2]출력 -> return;
[Com-1] i++ -> s=1, idx(i)=2 -> data[1] =3; ->재귀호출
[Com-3] s=2 -> s==r -> [1,3]출력 -> return;
[Com-1] i++ -> s=1, idx(i)=3(*for문 종료) -> data[1] =4; ->재귀호출
[Com-4] s=2 (s==r) -> [1,4]출력 -> return;

[Com] (starting함수) i++ -> s=0, idx(i)=1 -> data[0] =2; ->재귀호출
[Com-5] s=1, idx(i)=2 -> data[1] =3; ->재귀호출
[Com-6] s=2 (s==r) -> [2,3]출력 -> return;
[Com-5] i++ -> s=1, idx(i)=3(*for문 종료) -> data[1] =4; ->재귀호출
[Com-7] s=2 (s==r) -> [2,4]출력 -> return;

[Com] i++ -> s=0, idx(i)=2 -> data[0] =3;
.
.
.

이런 과정을 거쳐 data[0]의자리에 배열(arr)의 요소들이 차례로 위치하게 된다.

과정을 돌아보니 for문이 i=3일때 종료되었다. i=3일때 s=1이고 즉(1 >= 1)일때까지 반복된다. 이유는 i=4일때는 배열의 아이템 개수(4) - 4 = 0 이므로 r-s보다 같거나 클 수 없기 때문이다. r(2)-s는 1이하가 될 수 없다 -> 재귀함수 종료 조건이 s==r이기 때문에 s는 최대 1로 들어온다.