Find all permutations of an array - Where am I going wrong?

Question

So we have an array and I need to find all the permutations of the items in it.

for e.g, arr = [1, 2] should return [[1, 2], [2,1]]

Now here's my thought process:

If the array is empty, it should return [] which gives me the base condition.

if(arr.length === 0) return [];

Now we can further break the problem like this:

permutation([item1, item2]) = [[item1, ...permutation(item2)], [item2, ...permutation(item1)]

// permutation([1, 2, 3]) = [[1, ...permutation(2,3)], [2, ...permutation(1,3)], [3, ...permutation(1,3)]

So with that I tried to code:

function findPermutation(arr){

  function permute(arr){
    if(arr.length === 0) return [];//empty array base condition
    var res= [];
    for(let el of arr){
      //Reducing the array
      var filteredArray = arr.filter(a=> a!== el);
      //taking recursive leap of faith
      var temp = permute(filteredArray);
      res.push([el, ...(temp)])
    }
    
    //I suspect the problem could be here. It doesn't result
   //correctly so final output remains incorrect
    return res;
  }
  
  return permute(arr);
}
console.log(findPermutation([1, 2, 3]))

But somehow I'm making some mistakes in returning the res which is resulting in giving wrong results.

Where am I going wrong and is the above thought process correct?

Answer 1

The approach which you're following is correct. However, there needs a slight modification in your implementation. So, when you push the element into the res array, you need to push it into an array combined with each of the sub-permutations returned by the permute(filteredArray) call. One way to achieve this is by using a nested loop.

Analysis of the proposed implementation:

When we call permute(filteredArray), it returns an array of all possible permutations of the filteredArray (our leap of faith). Since each element from the original array will have its unique set of sub-permutations, we need to iterate through all these sub-permutations and prepend the current element (el) to each of these sub-permutations. For instance, let's take a look at the array [1, 2, 3]. Now, let's take 1 under consideration:

1. Pick the first element 1 and filter the array to get [2, 3]. Now we call permute([2, 3]) to get the sub-permutations: [[2, 3], [3, 2]](faith).

2. We need to prepend the element 1 to each of the sub-permutations: [[1, 2, 3], [1, 3, 2]]. This is why we use a nested loop to iterate through the subPermutations returned by the permute(filteredArray) call.

Using the spread syntax ...subPermutations without looping(as per your code) through the sub-permutations would result in an incorrect combination, as it would not cover all possible permutations for each element.

function findPermutation(arr) {
  function permute(arr) {
    if (arr.length === 0) return [
      []
    ]; // Return array with an empty array

    const res = [];
    for (let el of arr) {
      const filteredArray = arr.filter(a => a !== el);
      const subPermutations = permute(filteredArray);

      // note the below loop
      for (let subPermutation of subPermutations) {
        res.push([el, ...subPermutation]);
      }
    }

    return res;
  }

  return permute(arr);
}

console.log(findPermutation([1, 2, 3]));