Need Help With Permutations

JavaScript
1

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.

2

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
https://www.youtube.com/channel/UCRqg-s4e2qu5ZHWZ2Aji05g
(only gaming and life videos, no coding or development for now, soon though)

Hope this helps,

Hirashiki Rafael.

1 Like
3

@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.

4

@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
5

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

6

@hiRafa

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

Thank you for taking the time to help me.

1 Like
8

@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
9

@hiRafa

Thank you for that clarification.

10

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