Permutation

주어진 문자열 또는 숫자열 대상으로 모든 경우의 수를 찾아내는 알고리즘

막상 이런 문제가 눈앞에 보이면 허둥지둥 되다가 시간을 많이 보내다 보니 코드로 남겨 본다.

• Permutation 은 경우의 수다

• 첫 글자를 Permutation 기능 내에서 고정시켜 나가면서 순환 시켜야 한다

상기 이미지를 보면 ABC가 들어왔을 경우 A를 고정시키고 BC를 다시 Permutation Method에 넣는 것을 볼수 있다.

해당 Permutation은 마지막 한자리가 남을 때까지 지속하면 된다.

그리고 다시 B를 고정시키고 AC와 C를 고정시키고 BA를 Permutation을 순환 시키는 방식으로 전체 Permutation을 구할 수 있다.

function permutation(str, l, r, result = []) {
    if (l == r) {
        result.push(str); //한글자만 남으면 Return
    } else {
        for (let i = l; i <= r; i++) {// l 왼쪽의 글자는 고정영역
            str = swap(str, l, i); //고정 영역을 제외한 B와C 에서 B 또는 C를 다음 고정 영역으로 설정
            permutation(str, l + 1, r, result); // B또는 C를 제외한 나머지를 Permutation
            str = swap(str,l,i); // 상기에서 swap된 str을 원상 복귀
        }
    }
    return result;

// str의 특정 영역을 교환
    function swap(str,left,right) {
        let arr = str.split('');
        let tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        return arr.join('');
    }
}

 사용 방법은 아래와 같다

let str = 'abcd';
console.assert(permutation(str, 0, str.length - 1).length == factorial(str.length));

function factorial(n) {
    var result = 1;
    for(var i=2; i<=n; i++) result *= i;
    return result;
}

factorial과 동일한 갯수의 결과 Array가 나오면 된다.