How to insert an element into all positions in an array using recursion?

Question

I need to accomplish the following task using recursion:

Declare a function insert_all_positions, which takes for arguments: an element, x, and an array, arr. Functions must return an array of arrays, with each array corresponding to arrs with x inserted in a possible position. That is, if arr is the length N, then the result is an array with N + 1 arrays.

For example, the result of insert_all_positions (10, [1,2,3]) is the array:

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

I have this code so far:

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

    }
}

Answer 1

Here's a pure recursion.

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)))

Answer 2

You can use recursion by cloning, and adding the x element at the index (i) place, and then calling the function with the same parameters and incremented 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)

to solve this without recursion, I would use Array.from(), and create an array with a length of original arr length + 1:

function insert_all_positions (x, arr) {
  return Array.from({ length: arr.length + 1 }, (_, i) => 
    [...arr.slice(0, i), x, ...arr.slice(i)]
  );
}

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

console.log(result)

Answer 3

You don't have to use recursion to do this. But this function should return what you are looking for:

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 4

You can add the result as a parameter that can be passed in. Then you will be able to do the following:

1. (Termination step) if the result is equal to N + 1, you have generated all arrays and you're done.
2. Create a brand new array for the result.
3. Create a new array inserting x at an appropriate position
   • You can use the fact that the correct position for x is the current length of the result - first it's 0, next time it's 1, etc.
4. Construct a new result that uses the array you've created above.
5. (Recursion step) call insert_all_position supplying the new result as parameter.

This can look like this

//create an empty array for `result` initially
function insert_all_positions (x, arr, result = []) {
    //terminate - we're done
    if (arr.length + 1 == result.length)
      return result;
    
    //create a new array from `arr` with `x` in its proper place
    const insertIndex = result.length;
    const newArray = arr
      .slice(0, insertIndex)
      .concat(x)
      .concat(arr.slice(insertIndex));
    
    //construct the new result
    const newResult = [...result,  newArray];
    
    //recursive call
    return insert_all_positions(x, arr, newResult)
}

console.log(insert_all_positions(10, [1,2,3]))

Answer 5

A pure recursion.

The recursion works from the inserted value 10 as smallest array for an empty array.

The empty array is the exit condition and if no more items of the array are available, only a nested array with the insert value is returned.

For each recursive step, an array with wanted values is extended with the result of the recursive call and this array is mapped with either the insertation value or the first value of the array which is cutted of for the recursive call.

Here this result of the recursion is the right lower matrix.

result       comment
-----------  ----------------------------------

         10  insert(10, []), no more recursions


      10| 3  insert(10, [3])
      --+--
       3|10    > result of the recursion


   10| 2  3  insert(10, [2, 3])
   --+-----
    2|10  3    \ result of the recursion
    2| 3 10    /


10| 1  2  3  insert(10, [1, 2, 3])
--+--------
 1|10  2  3     \ result of the recursion
 1| 2 10  3     /
 1| 2  3 10    /

function insert(x, array) {
    if (!array.length) return [[x]];
    return [array, ...insert(x, array.slice(1))].map((a, i) => [i ? array[0] : x, ...a]);
}

insert(10, [1, 2, 3]).forEach(a => console.log(...a));