TypeScriptで順列の関数を自作する

前提

今回自作する関数は、n個からr個とる順列です。
再帰を利用することで、問題をより小さな部分問題に分割することができます。
具体的には、ある要素を1つ選択した後に残りの部分に対して再帰的に順列を生成する、というように問題を分割することができます。
そのため、再帰を使用します。

ソースコード

permutation.ts

function permutation(setNumbers: number[], extractNumber: number): number[][] {
    let answer: number[][] = [];
    if (extractNumber === 1) {
        for (let i = 0; i < setNumbers.length; i++) {
            answer[i] = [setNumbers[i]];
        }
    } else {
        for (let i = 0; i < setNumbers.length; i++) {
            let subsetNumbers = setNumbers.slice(0);
            subsetNumbers.splice(i, 1);
            const subPermutations = permutation(subsetNumbers, extractNumber - 1);
            for (let j = 0; j < subPermutations.length; j++) {
                answer.push([setNumbers[i]].concat(subPermutations[j]));
            }
        }
    }
    return answer;
} 

解説

基底条件は、取り出し数（extractNumber）が1の時です。
その際は、残りの要素（setNumbers）を答えの配列（answer）に代入します。

それ以外の時は、setNumbersを先頭から順に削除し、それを再帰的にpermutation関数に渡し、残りの要素の順列と結合することで目的の2次元配列を取得できます。