順列組み合わせ JavaScript(ES2015)

その1

https://qiita.com/higuma/items/5af4e62bdf4df42ce673
を参考にJavaScript(ES2015)での順列組み合わせ関数を作成したのでメモとして残しておく。

以下のコードの解説の再帰処理の流れが参考になった。
https://qiita.com/higuma/items/5af4e62bdf4df42ce673#%E3%82%B3%E3%83%BC%E3%83%89%E3%81%AE%E8%A7%A3%E8%AA%AC

実装

// pre: 1st half of array
// post: 2nd half of array
const permutation = ({ result = [], pre = [], post, n = post.length }) => {
  if (n > 0) {
    post.forEach((_, i) => {
      const rest = [...post];
      const elem = rest.splice(i, 1);
      permutation({ result, pre: [...pre, ...elem], post: rest, n: n - 1});
    });
  } else {
    result.push(pre);
  }
  return result;
};

const array = [0, 1, 2, 3];
const results = permutation({ post: array });
console.log(results);

const results2 = permutation({ post: array, n: 2 });
console.log(results2);

結果

[ [ 0, 1, 2, 3 ],
  [ 0, 1, 3, 2 ],
  [ 0, 2, 1, 3 ],
  [ 0, 2, 3, 1 ],
  [ 0, 3, 1, 2 ],
  [ 0, 3, 2, 1 ],
  [ 1, 0, 2, 3 ],
  [ 1, 0, 3, 2 ],
  [ 1, 2, 0, 3 ],
  [ 1, 2, 3, 0 ],
  [ 1, 3, 0, 2 ],
  [ 1, 3, 2, 0 ],
  [ 2, 0, 1, 3 ],
  [ 2, 0, 3, 1 ],
  [ 2, 1, 0, 3 ],
  [ 2, 1, 3, 0 ],
  [ 2, 3, 0, 1 ],
  [ 2, 3, 1, 0 ],
  [ 3, 0, 1, 2 ],
  [ 3, 0, 2, 1 ],
  [ 3, 1, 0, 2 ],
  [ 3, 1, 2, 0 ],
  [ 3, 2, 0, 1 ],
  [ 3, 2, 1, 0 ] ]

[ [ 0, 1 ],
  [ 0, 2 ],
  [ 0, 3 ],
  [ 1, 0 ],
  [ 1, 2 ],
  [ 1, 3 ],
  [ 2, 0 ],
  [ 2, 1 ],
  [ 2, 3 ],
  [ 3, 0 ],
  [ 3, 1 ],
  [ 3, 2 ] ]

その2

その1を実装後に Generate permutations of JavaScript array のキーワードで検索していたら、以下の記事を発見した。

Implement All Permutations of a Set in JavaScript – InitJS
https://initjs.org/all-permutations-of-a-set-f1be174c79f8

その1とは処理フローが少し異なるが、上記の記事を参考に別の実装をしてみた。
引数がarrayのみで済んでいる。

実装

const permutation = (array) => {
  let result = [];
  if (array.length === 1) {
    result.push(array);
    return result;
  }
  for (let i = 0; i < array.length; i++) {
    const firstElem = array.slice(i, i + 1);
    const restElem = [
      ...array.slice(0, i),
      ...array.slice(i + 1),
    ];
    let innerPermutations = permutation(restElem);
    for (let j = 0; j < innerPermutations.length; j++) {
      result.push([...firstElem, ...innerPermutations[j]]);
    }
  }
  return result;
};

const array = [0, 1, 2, 3];
const results = permutation(array);
console.log(results);

結果

[ [ 0, 1, 2, 3 ],
  [ 0, 1, 3, 2 ],
  [ 0, 2, 1, 3 ],
  [ 0, 2, 3, 1 ],
  [ 0, 3, 1, 2 ],
  [ 0, 3, 2, 1 ],
  [ 1, 0, 2, 3 ],
  [ 1, 0, 3, 2 ],
  [ 1, 2, 0, 3 ],
  [ 1, 2, 3, 0 ],
  [ 1, 3, 0, 2 ],
  [ 1, 3, 2, 0 ],
  [ 2, 0, 1, 3 ],
  [ 2, 0, 3, 1 ],
  [ 2, 1, 0, 3 ],
  [ 2, 1, 3, 0 ],
  [ 2, 3, 0, 1 ],
  [ 2, 3, 1, 0 ],
  [ 3, 0, 1, 2 ],
  [ 3, 0, 2, 1 ],
  [ 3, 1, 0, 2 ],
  [ 3, 1, 2, 0 ],
  [ 3, 2, 0, 1 ],
  [ 3, 2, 1, 0 ] ]

参考

https://qiita.com/s-katsumasa/items/7b8ce83df22467f74c51
にも書いてあるが、Rubyの場合 Array#permutation があるが、JSでは同等のものはなさそう。
instance method Array#permutation (Ruby 2.5.0)
https://docs.ruby-lang.org/ja/latest/method/Array/i/permutation.html

その2の実装と似ている ↓
Generate permutations of JavaScript array - Stack Overflow
https://stackoverflow.com/questions/37579994/generate-permutations-of-javascript-array/43260158#43260158