JavaScriptで順列を生成するライブラリをつくる

はじめに
コード
解説
テストコード
npm packageとして公開
おわりに

はじめに

JavaScriptで配列の要素をすべて並び替えて、順列を生成するライブラリを作成したので、その過程を記事にしてみました。

既に多くの方が、npm packageとして公開されているのですが、コードを書いたので、ライブラリとして公開してみました。

www.npmjs.com

コード

function generatePermutations(arr, currentPermutation = []){
    if (arr.length === 0) {
        return [currentPermutation];
    }

    let permutations = [];
    for (let i = 0; i < arr.length; i++) {
      const remainingElements = arr.slice(0, i).concat(arr.slice(i + 1));
      const newPermutation = currentPermutation.concat(arr[i]);
      permutations = permutations.concat(generatePermutations(remainingElements, newPermutation));
    }
    return permutations;
}

module.exports = {
  generatePermutations
};

解説

function generatePermutations(arr, currentPermutation = []){

generatePermutationsという関数を定義し、引数には以下を指定します
arr : 元の配列
currentPermutation : 順列を追跡していくための空の配列

if (arr.length === 0) {
        return [currentPermutation];
    }

ここで、もし、arrの長さが0だった場合、currentPermutationを返します
再帰関数の終了条件です

    let permutations = [];

生成された順列を保存する空配列

 for (let i = 0; i < arr.length; i++) {
      const remainingElements = arr.slice(0, i).concat(arr.slice(i + 1));
      const newPermutation = currentPermutation.concat(arr[i]);
      permutations = permutations.concat(generatePermutations(remainingElements, newPermutation));
    }

arrの長さ文、ループを回します。
remainingElements : arrから、現在の要素を取り除いた新しい配列を生成している
　　　　　　　　　　arrの0番目の要素から、i - 1番目の要素までを取得
　　　　　　　　　　arr.slice(i + 1)で、i + 1番目の要素から、最後の要素を取得
　　　　　　　　　　concatメソッドで、その2つの部分配列を結合
　　　　　　　　　　現在のi番目の要素を除いた新しい配列が完成する

newPermutation : 現在の順列(currentPermutation)にarr[i]の要素を追加した新たな配列
permutations : 再帰的に順列生成の関数を呼び出し、その結果を順列リストに追加

それぞれの再帰のステップで、配列の1つの要素を指定し、その要素を固定し
その残りの要素ですべての順列を生成している
これをすべての要素で処理を実行している

テストコード

テストフレームワークのJestを使用し、テストのコードを書いてみました

const { generatePermutations } = require('../js/index.js');

describe('generatePermutations', () => {
    test('good permutations', () => {
        const input = [1, 2, 3];
        const expected = [
            [1, 2, 3],
            [1, 3, 2],
            [2, 1, 3],
            [2, 3, 1],
            [3, 1, 2],
            [3, 2, 1],
        ];

        const result = generatePermutations(input);
        expect(result).toEqual(expect.arrayContaining(expected));
        expect(result.length).toBe(expected.length);
    });

    test('empty array', () => {
        const input = [];
        const expected = [[]];

        const result = generatePermutations(input);
        expect(result).toEqual(expected);
    })