[algorithm] 순열(Permutation) 정리

모든 경우의 수를 순서대로 나열하는 방법인 순열을 정리한다.

순열이란?

순서가 있으면 순열, 순서가 없으면 조합이다.

순열을 계산하는 방법은 아래와 같다. 

그러나 경우의 수를 구하는 것 보다는, 경우의 리스트를 반환하는 방식으로 문제가 출제되는 것 같다. 

중복순열

순열과 다르게 중복순열은 중복을 허용한다.

코드

function main(nums) {
    let result = [];
    perm(result, nums, 0);
    return result;
}

function perm(result, nums, depth) {
    if (depth === nums.length) {
        result.push(nums.map(n => n)); //deep copy
        return result;
    }

    //swap and deep down
    for (let i = depth; i < nums.length; i++) {
        swap(nums, i, depth);
        perm(result, nums, depth + 1);
        swap(nums, i, depth);
    }
}

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

console.log(main([1, 2, 3]));
// [
//     [1, 2, 3],
//     [1, 3, 2],
//     [2, 1, 3],
//     [2, 3, 1],
//     [3, 2, 1],
//     [3, 1, 2]
// ]

느낀 점

1. 순열과 조합은 PS에서 단골로 출제되는 문제이므로 이해하지 못한다면 외워서라도 알고 있어야 한다.
2. 시간 복잡도가 매우 높은 편 O(n!)이므로 유의하자.

다음엔 조합(Combination) 을 정리해보도록 한다.