순열 구하기

분류: Permutation

문제

정수 배열이 주어졌을 때, 해당 배열의 순열을 구해서 반환하라

const arr = [1, 2, 3];

console.log(permute(arr));

// result
[
  [ 1, 2, 3 ],
  [ 2, 1, 3 ],
  [ 3, 1, 2 ],
  [ 1, 3, 2 ],
  [ 2, 3, 1 ],
  [ 3, 2, 1 ]
]

풀이

재귀로 푸는 방식이 있고, 그냥 loop를 돌면서 푸는 방식(Heap method)이 있다. javascript 특성 상 재귀보단 loop를 돌면서 구하는게 맞을거 같다라는 생각이 들었다.

다만 Heap method로 풀 경우 결과 값이 조금 달라지는데 이에 따라 정렬이 필요할 수 있을거 같단 생각이 들었다.

// Heap method로 풀 경우 결과 값
[ 1, 2, 3 ]
[ 2, 1, 3 ]
[ 3, 1, 2 ]
[ 1, 3, 2 ]
[ 2, 3, 1 ]
[ 3, 2, 1 ]

1. Recursion

const permute = (inputArr) => {
    const result = [];

    const _permute = (arr, m = []) => {
        if (arr.length === 0) {
            result.push(m)
        } else {
            for (let i = 0; i < arr.length; i++) {
                const curr = arr.slice();
                const next = curr.splice(i, 1);
                _permute(curr, m.concat(next))
            }
        }
    }

    _permute(inputArr)

    return result;
}

비교적 깔끔하게 순열을 구하는 로직이 작성된 것을 볼 수 있다.

2. Heap method

function permute(arr) {
    const length = arr.length,
        result = [ arr.slice() ],
        c = new Array(length).fill(0);

    let i = 1, k;

    while (i < length) {
        if (c[i] < i) {
            k = i % 2 && c[i];
            [arr[i], arr[k]] = [arr[k], arr[i]];

            ++c[i];
            i = 1;
            result.push(arr.slice());

        } else {
            c[i] = 0;
            ++i;
        }
    }
    return result;
}

Reference

https://stackoverflow.com/questions/9960908/permutations-in-javascript