Generate All Permutations of Array in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a permutation in the context of arrays?

A permutation is a way to arrange all elements of an array in every possible order without missing any arrangement.

intermediate

Which method is commonly used to generate all permutations of an array?

Backtracking is commonly used to generate all permutations by building permutations step-by-step and undoing choices to explore all possibilities.

intermediate

In generating permutations, why do we swap elements in the array?

Swapping elements helps to fix one element at a position and then recursively generate permutations for the rest, ensuring all unique orders are explored.

beginner

What is the base case in a recursive function that generates all permutations of an array?

The base case is when the current position reaches the end of the array, meaning a complete permutation is formed and can be recorded or printed.

beginner

How many permutations does an array of length n have?

An array of length n has n! (n factorial) permutations, which is the product of all positive integers up to n.

What does the backtracking approach do when generating permutations?

A Sorts the array and returns it

B Only swaps the first two elements

C Removes duplicates from the array

D Tries all possible element orders by swapping and then undoing swaps

Backtracking tries all possible orders by swapping elements and then swapping back to explore other possibilities.

When generating permutations, what should you do after swapping elements and recursively calling the function?

A Swap the elements back to restore the original order

B Leave the elements swapped

C Sort the array

D Remove the last element

Swapping back restores the original array so other permutations can be generated correctly.

If an array has 4 elements, how many total permutations are there?

A 4

B 24

C 16

D 8

4 elements have 4! = 4 × 3 × 2 × 1 = 24 permutations.

What is the stopping condition in a recursive permutation function?

A When the first element is fixed

B When the array is empty

C When the current index reaches the array length

D When the array is sorted

The recursion stops when the current index reaches the array length, meaning a full permutation is formed.

Which of these is NOT a step in generating permutations by swapping?

A Sort the array after each swap

B Recursively generate permutations for next index

C Swap current element with each element from current index to end

D Swap back to restore original order

Sorting after each swap is not part of the permutation generation process.

Explain how backtracking helps generate all permutations of an array.

Think about choosing one element at a time and exploring all options.

Describe the steps to generate all permutations of [1, 2, 3] using swapping.

Visualize fixing each element at the first position and permuting the rest.

Practice

1. What does generating all permutations of an array mean?

easy

A. Finding the largest element in the array

B. Listing all possible orders of the array elements

C. Removing duplicate elements from the array

D. Sorting the array in ascending order

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

   Generating permutations means listing every possible order of the array's elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option B

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all ways to arrange elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Believing permutations find max element

2. Which of the following is the correct syntax to start a recursive function for generating permutations in JavaScript?

easy

A. function permute(arr l r) { }

B. function permute(arr, l, r) => { }

C. permute function(arr, l, r) { }

D. function permute(arr, l, r) { }

Solution

1. Step 1: Recall JavaScript function syntax

   Functions are declared with the keyword 'function', parameters inside parentheses separated by commas.

2. Step 2: Check each option

   function permute(arr, l, r) { } uses correct syntax: function name, parameters with commas, and braces. function permute(arr, l, r) => { } uses arrow syntax incorrectly. permute function(arr, l, r) { } has wrong order. function permute(arr l r) { } misses commas.

3. Final Answer:

   function permute(arr, l, r) { } -> Option D

4. Quick Check:

   Correct function syntax = function permute(arr, l, r) { } [OK]

Hint: Use 'function name(params) { }' for recursive functions [OK]

Common Mistakes:

• Using arrow syntax without proper parameters
• Missing commas between parameters
• Incorrect function keyword placement

3. What is the output of the following code?

function permute(arr, l, r) {
  if (l === r) {
    console.log(arr.join(''));
  } else {
    for (let i = l; i <= r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];
      permute(arr, l + 1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];
    }
  }
}
permute(['A', 'B', 'C'], 0, 2);

medium

A. ABC, ACB, BAC, BCA, CAB, CBA

B. ABC, BAC, CAB

C. ABC only

D. SyntaxError

Solution

1. Step 1: Understand the recursive swapping

   The function swaps elements starting from index l to r, generating all permutations by recursive calls.

2. Step 2: Trace output for ['A','B','C']

   All 6 permutations of 3 elements are printed: ABC, ACB, BAC, BCA, CAB, CBA.

3. Final Answer:

   ABC, ACB, BAC, BCA, CAB, CBA -> Option A

4. Quick Check:

   All 3-element permutations = ABC, ACB, BAC, BCA, CAB, CBA [OK]

Hint: Swapping + recursion = all permutations [OK]

Common Mistakes:

• Missing swap back step causing wrong output
• Printing partial permutations only
• Confusing output order

4. Identify the error in this permutation function:

function permute(arr, l, r) {
  if (l === r) {
    console.log(arr.join(''));
  } else {
    for (let i = l; i < r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];
      permute(arr, l + 1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];
    }
  }
}
permute(['X', 'Y', 'Z'], 0, 2);

medium

A. The for loop should use i <= r instead of i < r

B. The swap syntax is incorrect

C. The base case condition should be l > r

D. The function should not use recursion

Solution

1. Step 1: Check loop boundary

   The loop runs from i = l to i < r, so it misses the last index r.

2. Step 2: Correct loop condition

   Changing to i <= r includes the last element, ensuring all permutations are generated.

3. Final Answer:

   The for loop should use i <= r instead of i < r -> Option A

4. Quick Check:

   Loop boundary must include r [OK]

Hint: Loop to r inclusive for full permutations [OK]

Common Mistakes:

• Using i < r misses last element
• Incorrect swap syntax causing errors
• Wrong base case stopping recursion early

5. Given an array with duplicate elements ['A', 'B', 'A'], how can you modify the permutation function to avoid printing duplicate permutations?

hard

A. Use a set to track and skip already generated permutations

B. Remove duplicates from the array before permutation

C. Sort the array and skip swapping identical elements at the same recursion level

D. No modification needed; duplicates are automatically avoided

Solution

1. Step 1: Understand duplicates in permutations

   Duplicates cause repeated permutations when identical elements are swapped.

2. Step 2: Skip swapping identical elements

   Sorting the array and checking if the element was already swapped at the current recursion level avoids duplicates.

3. Final Answer:

   Sort the array and skip swapping identical elements at the same recursion level -> Option C

4. Quick Check:

   Skip identical swaps after sorting to avoid duplicates [OK]

Hint: Sort + skip identical swaps to avoid duplicate permutations [OK]

Common Mistakes:

• Removing duplicates loses valid permutations
• Using set only after generating all permutations (inefficient)
• Assuming duplicates are avoided automatically