JavaScript로 배열 요소의 중복 순열을 생성하는 방법 완벽 정리

JavaScript에서 배열의 요소들을 활용해 지정된 길이의 모든 가능한 순열(중복 허용)을 구하는 방법을 알아보겠습니다.

문제 정의

첫 번째 인수로 리터럴 값들의 배열을, 두 번째 인수로 숫자를 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 두 번째 인수로 지정된 길이와 같은 길이를 가지는 배열들을 모두 담은 배열을 반환하며, 각 배열은 입력 배열 요소들로 만들 수 있는 모든 가능한 순열을 포함해야 합니다.

예시

입력 배열과 숫자가 다음과 같다고 가정해 보겠습니다.

const arr = ['k', 5];
const num = 3;

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = [
    [ 'k', 'k', 'k' ],
    [ 'k', 'k', 5 ],
    [ 'k', 5, 'k' ],
    [ 'k', 5, 5 ],
    [ 5, 'k', 'k' ],
    [ 5, 'k', 5 ],
    [ 5, 5, 'k' ],
    [ 5, 5, 5 ]
];

즉, 요소가 2개인 배열에서 길이 3인 순열을 구하면 2³ = 8가지 조합이 나옵니다. 이는 같은 요소를 여러 번 재사용할 수 있는 중복 순열(product) 방식입니다.

재귀를 활용한 해결 코드

다음은 재귀 호출을 사용하여 이 문제를 해결하는 코드입니다.

const arr = ['k', 5];
const num = 3;

const allPairs = (arr = [], num) => {
    const res = [];
    if(num === 0){
        return [[]];
    }
    const subResult = allPairs(arr, num - 1);
    for(let el of arr){
        for(let sub of subResult){
            res.push([el].concat(sub));
        }
    }
    return res;
}

console.log(allPairs(arr, num));

코드 동작 원리

이 알고리즘의 핵심 로직은 다음과 같습니다.

1. 기저 조건(Base Case): num이 0이 되면 빈 배열 하나를 담은 배열 [[]]을 반환합니다. 이는 길이가 0인 순열이 딱 하나 존재한다는 의미입니다.

2. 재귀 호출: num - 1로 자기 자신을 다시 호출하여 더 짧은 길이의 순열 결과를 먼저 얻습니다.

3. 조합 생성: 원본 배열의 각 요소 el을 재귀 결과의 모든 하위 배열 앞에 붙여 새로운 순열을 만들어 res에 추가합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 출력이 표시됩니다.

[
    [ 'k', 'k', 'k' ],
    [ 'k', 'k', 5 ],
    [ 'k', 5, 'k' ],
    [ 'k', 5, 5 ],
    [ 5, 'k', 'k' ],
    [ 5, 'k', 5 ],
    [ 5, 5, 'k' ],
    [ 5, 5, 5 ]
]

마무리

이처럼 재귀를 활용하면 중복을 허용하는 순열을 간결하게 구현할 수 있습니다. 참고로 결과 배열의 크기는 n^k(n은 배열 길이, k는 목표 길이)만큼 커지므로, 입력값이 클 경우 성능에 유의해야 합니다. 반복문 기반 구현이나 제너레이터(generator)를 활용하면 메모리 사용량을 줄일 수 있습니다.