如何使用递归将元素插入数组中的所有位置？

Question

我需要使用递归完成以下任务：

声明一个函数insert\u all\u positions（插入所有位置），该函数接受以下参数：一个元素x和一个数组arr。函数必须返回一个数组数组，每个数组对应于arr，其中x插入到可能的位置。也就是说，如果arr是长度N，则结果是具有N 1个数组的数组。

例如，插入所有位置（10、[1,2,3]）的结果是数组：

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

到目前为止，我有这个代码：

function insert_all_positions (x, arr) {
    if (arr.length === 1) {
        return arr.concat(x)
    }
    else {

    }
}

Answer 1

您不必使用递归来实现这一点。但此函数应返回您要查找的内容：

function insert_all_positions (x, arr) {
    const arrays = [];
    for (let i = 0; i <= arr.length; i++) {
        const value = [...arr.slice(0, i), x, ...arr.slice(i)];
        arrays.push(value);
    }
    return arrays
}

Answer 2

您可以通过克隆来使用递归，并在索引（i）处添加x元素，然后调用具有相同参数并递增i的函数：

function insert_all_positions (x, arr, i = 0) {
  const clone = [...arr] // clone the array
  
  clone.splice(i, 0, x) // add the item at place i
  
  return i < clone.length - 1 ? // if still under the full length
    [clone, ...insert_all_positions(x, arr, i + 1)] // return current and next item/s
    :
    [clone] // return only current
}

const result = insert_all_positions (10, [1,2,3])

console.log(result)

Answer 3

这是一个纯递归。

function f(x, A){
  return A.length ? [[x, ...A]].concat(
    f(x, A.slice(1)).map(e => [A[0]].concat(e))) : [[x]]
}

var x = 10
var A = [1, 2, 3]

console.log(JSON.stringify(f(x, A)))