Edited at

順列組み合わせ 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