# Need Help With Permutations

Hello,

I have this solution for coming up with all the permutations of an array of numbers.

Here is my code:

``````function getPermutations(arr) {
let result = [];
let copy = arr.slice();

function permute(index) {
if (index === arr.length) {
result.push(copy.slice());
return;
}
for (let i = index; i < copy.length; i++) {
[copy[index], copy[i]] = [copy[i], copy[index]]; *
permute(index + 1);
[copy[index], copy[i]] = [copy[i], copy[index]]; **
}
}

permute(0);

return result;
}
``````

I am having some trouble understanding what is going on inside the `for` loop. Line * swaps one `index` of the copied array with an index `i`, and then recursively calls `permute()` with the next `index` until it reaches the base case `index === arr.length - 1`, when it then pushes the permuted array to `result`. I am guessing that all these recursive calls return before line ** runs, when the array is restored to its original [?] order and we move on to the next iteration of the `for` loop.

If that is the case, why canâ€™t I replace line ** with `copy = arr.slice()`? It doesnâ€™t work when I do that.

If line * is swapping one pair, waiting for all the recursive calls of `permute()` to return, and then swapping the pair back, wouldnâ€™t every subsequent iteration of the `for` loop be acting on the original array?

Is there something Iâ€™m missing?

Thank you.

The line `copy = arr.slice()` makes a shallow copy of the `arr` array and assigns it to the `copy` variable. This line is responsible for creating a separate copy of the array at the beginning of the `getPermutations` function, ensuring that subsequent modifications to `copy` do not affect the original `arr` array.

However, the swapping operation `[copy[index], copy[i]] = [copy[i], copy[index]]` is necessary to generate permutations within the `permute` function. It swaps the elements within the `copy` array to create different permutations by permuting the elements at different indices.

If you simply replace the swapping operation with `copy = arr.slice()`, it would not achieve the desired effect of generating permutations. The elements would remain in their original order, and the recursive calls within the `permute` function would not explore different combinations of elements.

Therefore, itâ€™s important to use the swapping operation `[copy[index], copy[i]] = [copy[i], copy[index]]` to properly generate permutations. The line `copy = arr.slice()` is unrelated and serves a different purpose of creating a copy of the array at the beginning of the function.

Basically before proceeding to [copy[index], copy[i]] = [copy[i], copy[index]]; **, the permute function is called entirely again, becoming something like this on the second time:

``````  function permute(index) {
if (index === arr.length) {
result.push(copy.slice());
return;
}
for (let i = index; i < copy.length; i++) {
[copy[index], copy[i]] = [copy[i], copy[index]]; *

// permute(index + 1);
if (index === arr.length) {
result.push(copy.slice());
return;
}
for (let i = index; i < copy.length; i++) {
[copy[index], copy[i]] = [copy[i], copy[index]]; *

//  permute(index + 1);
// again here until the first condition is met
// then when the condition is met, the function starts running the last line of the code which is this one below for every time the function permute was called, reordering  the elements back to its original position based on the position that it was within the time it was called.
// if the permute function was called 4 times, elements original positions within each time are different. so on 4th time elements [v,x,y,z] would be in a different position than on 3rd time, than on 2nd time, than on 1st time.
// it is almost like a ctrl + z, rewiring backwards
[copy[index], copy[i]] = [copy[i], copy[index]]; **
}
}
[copy[index], copy[i]] = [copy[i], copy[index]]; **
}
``````

Find me at: hiRafa (HIRASHIKI RAFAEL) Â· GitHub
or
(only gaming and life videos, no coding or development for now, soon though)

Hope this helps,

Hirashiki Rafael.

1 Like

@hiRafa

So, how I am understanding this, is that line ** doesnâ€™t just revert the copy array back to its state in line *.

Because the recursive calls to permute() modify the copy array further, the swap-backed copy array in line ** is a completely different array from the copy in line *.

And then the for loop continues on a slightly permuted copy array, not a copy of the original array.

@josephylee

Hi joseph

The line `**` doesnâ€™t simply revert the `copy` array back to its state in line `*`. Due to the recursive calls to `permute()`, the `copy` array is further modified, and the `swap`-backed `copy` array in line `**` becomes a distinct array from the `copy` array in line `*`.

Each recursive call to `permute()` generates permutations by swapping elements and exploring different combinations. As a result, the `copy` array is modified during each recursive call, leading to a different permutation arrangement.

When the recursive calls finish and the function starts executing the last line of code (line `**`), the swapping operation reverts the `copy` array to its original state within that specific recursive call. This restoration of elementsâ€™ original positions ensures that subsequent iterations of the loop in the previous recursive call explore different combinations.

In summary, the `for` loop continues on a slightly permuted `copy` array, which is the result of the previous recursive call, not a copy of the original array. Each recursive call modifies the `copy` array, and the last line (`**`) restores it to its previous state within that specific recursive call, allowing for correct permutation generation.

Let me provide a step-by-step breakdown of the process:
Given an array with 3 elements [a,x,f]

1. Initial call: `permute(0)`.
2. The loop iteration begins with `i = 0`.
• The swapping operation `[copy[0], copy[i]] = [copy[i], copy[0]]` is performed, modifying the `copy` array.
• The recursive call `permute(0 + 1) = permute(1)` is made.
1. The `permute(1)` call starts, and the loop iteration begins with `i = 0`.
• The swapping operation is performed, modifying the `copy` array.
• The recursive call `permute(1 + 1) = permute(2)` is made.
1. The `permute(2)` call starts, and the loop iteration begins with `i = 0`.
• The swapping operation is performed, modifying the `copy` array.
• The recursive call `permute(2 + 1) = permute(3)` is made.
1. The `permute(3)` call starts, and since `index === arr.length`, the base case is met.
• The current permutation is added to the `result` array.
• The function starts unwinding back to the previous recursive call (`permute(2)`).
1. Upon reaching the line `**` in `permute(2)`, the swapping operation is performed, restoring the elements to their original positions within the `permute(2)` recursive call.
• The function continues unwinding back to the previous recursive call (`permute(1)`).
1. Upon reaching the line `**` in `permute(1)`, the swapping operation is performed, restoring the elements to their original positions within the `permute(1)` recursive call.
• The function continues unwinding back to the initial recursive call (`permute(0)`).
1. Upon reaching the line `**` in `permute(0)`, the swapping operation is performed, restoring the elements to their original positions within the `permute(0)` recursive call.
• The function continues with the loop iteration, proceeding to the next value of `i`.
1. The loop continues with `i = 1`.
• The swapping operation is performed, modifying the `copy` array.
• The recursive call `permute(1)` is made again.
1. The loop continues until all iterations are completed.
2. Once the loop finishes, the function returns, and the `result` array contains all generated permutations.
1 Like

So I donâ€™t even know what this means, can you please help me with thisâ€¦ thanks for the right thing to do with
details of [quote=â€śjosephylee, post:1, topic:611512, full:trueâ€ť]
Hello,

I have this solution for coming up with all the permutations of an array of numbers.

Here is my code:

``````function Generations(arr) {
let result = [];
let copy = arr.slice();

function permute(index) {
if (index === arr.length) {
result.push(copy.slice());
return;
}
for (let i = index; i < copy.length; i++) {
[copy[index], copy[i]] = [copy[i], copy[index]]; *
permute(index + 1);
[copy[index], copy[i]] = [copy[i], copy[index]]; **
}
}

permute(0);

return result;
}
``````

I am having some trouble understanding what is going on inside the `for` loop. Line * swaps one `index` of the copied array with an index `i`, and then recursively calls `permute()` with the next `index` until it reaches the base case `index === arr.length - 1`, when it then pushes the permuted array to `result`. I am guessing that all these recursive calls return before line ** runs, when the array is restored to its original [?] order and we move on to the next iteration of the `for` loop.

If that is the case, why canâ€™t I replace line ** with `copy = arr.slice()`? It doesnâ€™t work when I do that.

If line * is swapping one pair, waiting for all the recursive calls of `permute()` to return, and then swapping the pair back, wouldnâ€™t every subsequent iteration of the `for` loop be acting on the original array?

Is there something Iâ€™m missing?

Thank you.
[/quote]

what I can do

@hiRafa

That was a great explanation. I understand what is happening, now.

Thank you for taking the time to help me.

1 Like

@josephylee
Going over my explanation I noticed a mistake.
I forgot to mention the reloop for when variable â€śiâ€ť is still below the arr.length, which in this case is 3.
Iâ€™m breaking down the function with a proper explanation

``````      function getPermutations(arr) {
let result = [];
let copy = arr.slice();

function permute(index) {
if (index === arr.length) {
console.log("pusshing", copy.slice())
result.push(copy.slice());
return;
}
for (let i = index; i < copy.length; i++) {
[copy[index], copy[i]] = [copy[i], copy[index]];

//permute (1)
if (1 === arr.length) {
console.log("pusshing", copy.slice())
result.push(copy.slice());
return;
}

for (let i = 1; i < copy.length; i++) {
[copy[1], copy[i]] = [copy[i], copy[1]];

//permute (2)
if (2 === arr.length) {
console.log("pusshing", copy.slice())
result.push(copy.slice());
return;
}
for (let i = 2; i < copy.length; i++) {
[copy[2], copy[i]] = [copy[i], copy[2]];

//permute (3)
if (3 === arr.length) {
console.log("pusshing", copy.slice())
result.push(copy.slice());
return;
}
// condition met, for loop 3 ignored.
// ['a', 'x', 'f'] is pushed

[copy[1], copy[i]] = [copy[i], copy[1]];
// permute(2) rewind, i++ equals 3, so loop 2 ends
}
[copy[1], copy[i]] = [copy[i], copy[1]];
// permute(1) rewind, i++ equals 2, so loop 1 runs one more time
// at the end of the loop
// ['a', 'f', 'x'] is pushed
}

[copy[index], copy[i]] = [copy[i], copy[index]];
// permute(0) rewinds back to its original state, loop 0 runs again for 1, 2 and 3. On three is ends definetely.
}
}

permute(0);

return result;
}

// Example usage
const input = ["a", "x", "f"];
const permutations = getPermutations(input);
console.log(permutations);

``````
1 Like

@hiRafa

Thank you for that clarification.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.