javascriptalgorithmrecursionpermutation

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

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?

Solution

• 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]));``````