Generate All Permutations of Array in DSA C++ - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with full array

↓

Choose element at index i

↓

Swap element i with element j (j >= i)

↓

Recurse on subarray from i+1

↓

If i == end, output current permutation

↓

Backtrack: swap back elements i and j

↩Back to choose next j

We pick each element in turn, swap it to the current position, recurse on the rest, then swap back to restore the array.

Execution Sample

DSA C++

void permute(vector<int>& arr, int start) {
  if (start == arr.size()) {
    print(arr);
    return;
  }
  for (int i = start; i < arr.size(); i++) {
    swap(arr[start], arr[i]);
    permute(arr, start + 1);
    swap(arr[start], arr[i]);
  }
}

This code generates all permutations by swapping elements starting from index 'start' and recursing.

Execution Table

Step	Operation	Current Index (start)	Swapped Indices	Array State	Action
1	Start permute	0	-	[1, 2, 3]	Begin with full array
2	Swap	0	0,0	[1, 2, 3]	Swap element 0 with 0 (no change)
3	Recurse	1	-	[1, 2, 3]	Recurse with start=1
4	Swap	1	1,1	[1, 2, 3]	Swap element 1 with 1 (no change)
5	Recurse	2	-	[1, 2, 3]	Recurse with start=2
6	Swap	2	2,2	[1, 2, 3]	Swap element 2 with 2 (no change)
7	Recurse	3	-	[1, 2, 3]	start == size, output permutation
8	Backtrack	2	2,2	[1, 2, 3]	Swap back element 2 with 2
9	Backtrack	1	1,1	[1, 2, 3]	Swap back element 1 with 1
10	Swap	1	1,2	[1, 3, 2]	Swap element 1 with 2
11	Recurse	2	-	[1, 3, 2]	Recurse with start=2
12	Swap	2	2,2	[1, 3, 2]	Swap element 2 with 2 (no change)
13	Recurse	3	-	[1, 3, 2]	start == size, output permutation
14	Backtrack	2	2,2	[1, 3, 2]	Swap back element 2 with 2
15	Backtrack	1	1,2	[1, 2, 3]	Swap back element 1 with 2
16	Backtrack	0	0,0	[1, 2, 3]	Swap back element 0 with 0
17	Swap	0	0,1	[2, 1, 3]	Swap element 0 with 1
18	Recurse	1	-	[2, 1, 3]	Recurse with start=1
19	Swap	1	1,1	[2, 1, 3]	Swap element 1 with 1 (no change)
20	Recurse	2	-	[2, 1, 3]	Recurse with start=2
21	Swap	2	2,2	[2, 1, 3]	Swap element 2 with 2 (no change)
22	Recurse	3	-	[2, 1, 3]	start == size, output permutation
23	Backtrack	2	2,2	[2, 1, 3]	Swap back element 2 with 2
24	Backtrack	1	1,1	[2, 1, 3]	Swap back element 1 with 1
25	Swap	1	1,2	[2, 3, 1]	Swap element 1 with 2
26	Recurse	2	-	[2, 3, 1]	Recurse with start=2
27	Swap	2	2,2	[2, 3, 1]	Swap element 2 with 2 (no change)
28	Recurse	3	-	[2, 3, 1]	start == size, output permutation
29	Backtrack	2	2,2	[2, 3, 1]	Swap back element 2 with 2
30	Backtrack	1	1,2	[2, 1, 3]	Swap back element 1 with 2
31	Backtrack	0	1,0	[1, 2, 3]	Swap back element 1 with 0
32	Swap	0	0,2	[3, 2, 1]	Swap element 0 with 2
33	Recurse	1	-	[3, 2, 1]	Recurse with start=1
34	Swap	1	1,1	[3, 2, 1]	Swap element 1 with 1 (no change)
35	Recurse	2	-	[3, 2, 1]	Recurse with start=2
36	Swap	2	2,2	[3, 2, 1]	Swap element 2 with 2 (no change)
37	Recurse	3	-	[3, 2, 1]	start == size, output permutation
38	Backtrack	2	2,2	[3, 2, 1]	Swap back element 2 with 2
39	Backtrack	1	1,1	[3, 2, 1]	Swap back element 1 with 1
40	Swap	1	1,2	[3, 1, 2]	Swap element 1 with 2
41	Recurse	2	-	[3, 1, 2]	Recurse with start=2
42	Swap	2	2,2	[3, 1, 2]	Swap element 2 with 2 (no change)
43	Recurse	3	-	[3, 1, 2]	start == size, output permutation
44	Backtrack	2	2,2	[3, 1, 2]	Swap back element 2 with 2
45	Backtrack	1	1,2	[3, 2, 1]	Swap back element 1 with 2
46	Backtrack	0	2,0	[1, 2, 3]	Swap back element 2 with 0
47	End	-	-	[1, 2, 3]	All permutations generated

💡 All indices swapped and recursed, permutations complete

Variable Tracker

Variable	Start	After Step 2	After Step 10	After Step 17	After Step 25	After Step 32	Final
arr	[1, 2, 3]	[1, 2, 3]	[1, 3, 2]	[2, 1, 3]	[2, 3, 1]	[3, 2, 1]	[1, 2, 3]
start	0	0	0	0	0	0	-
i (loop index)	-	0	2	2	2	2	-

Key Moments - 3 Insights

Why do we swap back the elements after recursion?

Swapping back restores the array to its original state before the next iteration, as shown in steps 8, 15, 30, 39, 45, and 46 in the execution_table.

What happens when start equals the array size?

When start equals the array size (step 7, 13, 22, 28, 37, 43), the current array state is a complete permutation and is output.

Why do we swap elements at indices start and i?

Swapping elements at start and i moves each possible element into the current position to explore all permutations, as seen in steps 2, 10, 17, 25, and 32.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the array state?

A [1, 2, 3]

B [2, 1, 3]

C [1, 3, 2]

D [3, 2, 1]

💡 Hint

Check the 'Array State' column at step 10 in the execution_table.

At which step does the recursion first output a permutation?

A Step 7

B Step 13

C Step 22

D Step 37

💡 Hint

Look for 'start == size, output permutation' in the Action column.

If we skip swapping back after recursion, what happens to the array state at step 15?

A [1, 2, 3]

B [1, 3, 2]

C [2, 1, 3]

D [3, 1, 2]

💡 Hint

Refer to the Backtrack action at step 15 which swaps back to restore [1, 2, 3]. Without it, the array remains [1, 3, 2].

Concept Snapshot

Generate All Permutations of Array:
- Use recursion with a 'start' index.
- Swap each element from 'start' to end with 'start'.
- Recurse with start+1.
- When start == array size, output permutation.
- Swap back after recursion to restore array.
- This explores all possible orderings systematically.

Full Transcript

This visualization shows how to generate all permutations of an array by swapping elements starting from a 'start' index. At each step, we swap the element at 'start' with each element from 'start' to the end, recurse to generate permutations of the remaining elements, then swap back to restore the original array. When the 'start' index reaches the array size, the current array is a complete permutation and is output. The execution table tracks each swap, recursion, and backtrack step, showing the array state and actions. Key moments clarify why swapping back is necessary and when permutations are output. The visual quiz tests understanding of array states at specific steps and the importance of backtracking. This method ensures all permutations are generated without duplicates or missing any orderings.

Practice

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

easy

A. Listing all possible orders of the array elements

B. Sorting the array in ascending order

C. Finding the maximum element in the array

D. Removing duplicate elements from the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

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

3. Final Answer:

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

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all possible orders of elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Assuming permutations find max or min

2. Which of the following C++ function signatures is correct for a recursive function generating all permutations of an integer array arr with size n</> and current index start?

easy

A. void permute(int arr[], int start, int n)

B. int permute(int arr[], int n, int start)

C. void permute(int arr[], int n)

D. int permute(int arr[], int start)

Solution

1. Step 1: Check parameter order and types

   The function needs the array, current index (start), and total size (n) to generate permutations recursively.

2. Step 2: Validate return type and parameters

   It should return void (no value) and have parameters (int arr[], int start, int n) in that order.

3. Final Answer:

   void permute(int arr[], int start, int n) -> Option A

4. Quick Check:

   Correct signature = void permute(arr, start, n) [OK]

Hint: Recursive permute needs array, start index, and size [OK]

Common Mistakes:

• Wrong parameter order
• Incorrect return type
• Missing current index parameter

3. What will be the output of the following C++ code snippet?

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = start; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

int main() {
  int arr[] = {1, 2};
  permute(arr, 0, 2);
  return 0;
}

medium

A. 2 1 \n 1 2 \n

B. 1 2 \n 2 1 \n

C. 1 2 \n 1 2 \n

D. No output

Solution

1. Step 1: Trace first call with arr = {1, 2}

   Start = 0, n = 2. Swap arr[0] with arr[0] (no change), call permute with start=1.

2. Step 2: Trace second call with start=1

   Swap arr[1] with arr[1] (no change), call permute with start=2 which prints "1 2".

3. Step 3: Backtrack and swap arr[0] with arr[1]

   Array becomes {2, 1}, call permute with start=1 again.

4. Step 4: At start=1 again, swap arr[1] with arr[1], call permute with start=2 prints "2 1".

5. Final Answer:

   1 2 \n 2 1 \n -> Option B

6. Quick Check:

   All permutations of {1,2} printed [OK]

Hint: Swap and backtrack to print all orders [OK]

Common Mistakes:

• Not swapping back after recursion
• Printing before base case
• Incorrect loop range

4. Identify the error in the following code snippet for generating permutations of array arr of size n:

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = 0; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

medium

A. Function should return int, not void

B. Base case condition should be start == n - 1

C. Swap should be done only once outside the loop

D. Loop should start from i = start, not 0

Solution

1. Step 1: Analyze the for loop range

   The loop swaps arr[start] with arr[i]. If i starts at 0 always, it swaps elements already fixed in previous recursion steps.

2. Step 2: Correct loop start index

   Loop should start from i = start to avoid repeating swaps and ensure correct permutations.

3. Final Answer:

   Loop should start from i = start, not 0 -> Option D

4. Quick Check:

   Loop from start to n fixes correct elements [OK]

Hint: Start loop from current index to avoid duplicate swaps [OK]

Common Mistakes:

• Starting loop from 0 causes repeated permutations
• Changing base case incorrectly
• Misplacing swap calls

5. Given an array arr = {1, 2, 2}, how many unique permutations will a correct C++ program generate if it avoids duplicates?

hard

A. 2

B. 6

C. 3

D. 4

Solution

1. Step 1: Calculate total permutations without duplicates

   For 3 elements with two 2's, total permutations = 3! / 2! = 3.

2. Step 2: List unique permutations

   They are {1,2,2}, {2,1,2}, {2,2,1} -- total 3 unique permutations.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3! / 2! = 3 unique permutations [OK]

Hint: Divide factorial by duplicates factorial for unique count [OK]

Common Mistakes:

• Counting duplicates as unique permutations
• Using 3! = 6 without division
• Ignoring repeated elements