JavaScriptで再帰を使って配列のすべての位置に要素を挿入する方法

要素 x と配列 arr を引数として受け取る関数、たとえば insertAllPositions を定義する必要があります。

この関数は「配列の配列」を返し、それぞれの内側の配列は、元の配列 arr の可能なすべての位置に要素 x を挿入した結果に対応します。

つまり、arr の長さが N である場合、結果は N + 1 個の配列を含む配列になります。

例えば、insertAllPositions(10, [1,2,3]) の結果は次のようになります −

const output = [
   [10,1,2,3],
   [1,10,2,3],
   [1,2,10,3],
   [1,2,3,10]
];

純粋な再帰だけで実装する

この関数は、ループを使用せずに再帰呼び出しだけで記述する必要があります。以下がそのコード例です −

const arr = [1, 2, 3];
const num = 10;
const insertAllPositions = (num, arr) => {
   return arr.length ?
   [[num, ...arr]]
   .concat(insertAllPositions(num, arr.slice(1))
   .map(el => {
      return [arr[0]].concat(el);
   })) :
   [[num]]
};
console.log(insertAllPositions(num, arr));

出力

コンソールには次の出力が表示されます −

[ [ 10, 1, 2, 3 ], [ 1, 10, 2, 3 ], [ 1, 2, 10, 3 ], [ 1, 2, 3, 10 ] ]

コードの仕組み

この再帰的なアプローチでは、まず現在の配列の先頭（インデックス 0）に num を挿入した配列 [num, ...arr] を作成します。次に、先頭要素を除いた残りの配列 arr.slice(1) に対して同じ関数を再帰的に呼び出し、その結果得られる各配列の先頭に元の配列の最初の要素 arr[0] を付け加えることで、挿入位置を一つずつ後ろへずらしていきます。

ベースケースは配列が空になったときで、この場合には [[num]]（配列の末尾への挿入に相当する結果）を返します。これにより、長さ N の配列に対して、先頭から末尾までの N + 1 通りの挿入パターンがすべて生成されます。