Generate All Permutations of Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Permutation Generator

What is the output of the following JavaScript code that generates all permutations of the array [1, 2]?

DSA Javascript

function permute(arr) {
  if (arr.length === 0) return [[]];
  const first = arr[0];
  const rest = permute(arr.slice(1));
  const result = [];
  for (const perm of rest) {
    for (let i = 0; i <= perm.length; i++) {
      const newPerm = perm.slice(0, i).concat([first], perm.slice(i));
      result.push(newPerm);
    }
  }
  return result;
}
console.log(permute([1, 2]));

A [[1,2],[2,1]]

B [[2,1]]

C [[1,2]]

D [[2,1],[1,2]]

💡 Hint

Think about how the function inserts the first element into every possible position of smaller permutations.

The function recursively generates permutations by inserting the first element into every position of permutations of the rest of the array. For [1,2], it produces [[1,2],[2,1]].

❓ Predict Output

intermediate

Output of Permutation Using Heap's Algorithm

What is the output of this JavaScript code using Heap's algorithm to generate permutations of [1, 2, 3]?

DSA Javascript

function heapPermute(n, arr, result = []) {
  if (n === 1) {
    result.push(arr.slice());
  } else {
    for (let i = 0; i < n - 1; i++) {
      heapPermute(n - 1, arr, result);
      if (n % 2 === 0) {
        [arr[i], arr[n - 1]] = [arr[n - 1], arr[i]];
      } else {
        [arr[0], arr[n - 1]] = [arr[n - 1], arr[0]];
      }
    }
    heapPermute(n - 1, arr, result);
  }
  return result;
}
console.log(heapPermute(3, [1, 2, 3]));

A [[1,3,2],[1,2,3],[3,1,2],[3,2,1],[2,1,3],[2,3,1]]

B [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

C [[1,2,3],[2,1,3],[3,1,2],[1,3,2],[2,3,1],[3,2,1]]

D [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]]

💡 Hint

Heap's algorithm generates permutations by swapping elements based on parity of n.

Heap's algorithm produces permutations in the order: [1,2,3], [2,1,3], [3,1,2], [1,3,2], [2,3,1], [3,2,1].

🔧 Debug

advanced

Identify the Error in Permutation Code

What error will this JavaScript code produce when generating permutations of [1, 2, 3]?

DSA Javascript

function permute(arr) {
  if (arr.length === 0) return [];
  const first = arr[0];
  const rest = permute(arr.slice(1));
  const result = [];
  for (const perm of rest) {
    for (let i = 0; i <= perm.length; i++) {
      const newPerm = perm.slice(0, i).concat([first], perm.slice(i));
      result.push(newPerm);
    }
  }
  return result;
}
console.log(permute([1, 2, 3]));

A RangeError: Maximum call stack size exceeded

B TypeError: Cannot read property 'slice' of undefined

C Output: All permutations of [1, 2, 3]

D Output: [] (empty array)

💡 Hint

Check the base case return value and how it affects recursion.

The base case returns an empty array [], so the recursive call returns [] and the for loop over rest does not run, resulting in an empty array output.

🚀 Application

advanced

Number of Permutations for Array of Length 4

How many permutations will be generated for an array of length 4?

A 16

B 24

C 12

D 8

💡 Hint

Number of permutations of n distinct elements is n factorial (n!).

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

🧠 Conceptual

expert

Time Complexity of Generating All Permutations

What is the time complexity of generating all permutations of an array of length n?

A O(n!)

B O(n^2)

C O(2^n)

D O(n log n)

💡 Hint

Consider how many permutations exist and how much work is done per permutation.

There are n! permutations and generating each takes at least constant time, so total time is O(n!).

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