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 with i+1

↓

If i == array length - 1

↓

Print current permutation

↓

Backtrack: Swap back elements i and j

↩Back to swap step for next j

We pick each element in turn, swap it with the current position, recurse to fix the next position, print when done, then swap back to restore.

Execution Sample

DSA C

void permute(int *arr, int start, int end) {
  if (start == end) {
    print(arr, end + 1);
  } else {
    for (int i = start; i <= end; i++) {
      swap(arr[start], arr[i]);
      permute(arr, start+1, end);
      swap(arr[start], arr[i]);
    }
  }
}

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

Execution Table

Step	Operation	Indices Swapped	Current Array State	Action
1	Start permute	-	[1, 2, 3]	Call permute(arr, 0, 2)
2	Swap	(0,0)	[1, 2, 3]	Swap elements at 0 and 0
3	Recurse	-	[1, 2, 3]	Call permute(arr, 1, 2)
4	Swap	(1,1)	[1, 2, 3]	Swap elements at 1 and 1
5	Recurse	-	[1, 2, 3]	Call permute(arr, 2, 2)
6	Print	-	[1, 2, 3]	Print permutation
7	Backtrack	(1,1)	[1, 2, 3]	Swap back elements at 1 and 1
8	Swap	(1,2)	[1, 3, 2]	Swap elements at 1 and 2
9	Recurse	-	[1, 3, 2]	Call permute(arr, 2, 2)
10	Print	-	[1, 3, 2]	Print permutation
11	Backtrack	(1,2)	[1, 2, 3]	Swap back elements at 1 and 2
12	Backtrack	(0,0)	[1, 2, 3]	Swap back elements at 0 and 0
13	Swap	(0,1)	[2, 1, 3]	Swap elements at 0 and 1
14	Recurse	-	[2, 1, 3]	Call permute(arr, 1, 2)
15	Swap	(1,1)	[2, 1, 3]	Swap elements at 1 and 1
16	Recurse	-	[2, 1, 3]	Call permute(arr, 2, 2)
17	Print	-	[2, 1, 3]	Print permutation
18	Backtrack	(1,1)	[2, 1, 3]	Swap back elements at 1 and 1
19	Swap	(1,2)	[2, 3, 1]	Swap elements at 1 and 2
20	Recurse	-	[2, 3, 1]	Call permute(arr, 2, 2)
21	Print	-	[2, 3, 1]	Print permutation
22	Backtrack	(1,2)	[2, 1, 3]	Swap back elements at 1 and 2
23	Backtrack	(0,1)	[1, 2, 3]	Swap back elements at 0 and 1
24	Swap	(0,2)	[3, 2, 1]	Swap elements at 0 and 2
25	Recurse	-	[3, 2, 1]	Call permute(arr, 1, 2)
26	Swap	(1,1)	[3, 2, 1]	Swap elements at 1 and 1
27	Recurse	-	[3, 2, 1]	Call permute(arr, 2, 2)
28	Print	-	[3, 2, 1]	Print permutation
29	Backtrack	(1,1)	[3, 2, 1]	Swap back elements at 1 and 1
30	Swap	(1,2)	[3, 1, 2]	Swap elements at 1 and 2
31	Recurse	-	[3, 1, 2]	Call permute(arr, 2, 2)
32	Print	-	[3, 1, 2]	Print permutation
33	Backtrack	(1,2)	[3, 2, 1]	Swap back elements at 1 and 2
34	Backtrack	(0,2)	[1, 2, 3]	Swap back elements at 0 and 2
35	End	-	[1, 2, 3]	All permutations generated

💡 All swaps and recursions completed, original array restored

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 13	After Step 19	After Step 24	After Step 30	Final
arr	[1,2,3]	[1,2,3]	[1,3,2]	[2,1,3]	[2,3,1]	[3,2,1]	[3,1,2]	[1,2,3]
start	0	1	1	1	1	1	1	-
end	2	2	2	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 like 7, 11, 22, 23, 33, and 34 in the execution_table.

Why do we recurse only when start < end?

When start == end (step 5, 9, 16, 20, 27, 31), we have fixed all positions and print the permutation. No further recursion is needed.

How does swapping elements generate all permutations?

By swapping each element into the current 'start' position and recursing, we explore all possible orders. The execution_table shows different swaps at steps 2, 8, 13, 19, 24, and 30.

Visual Quiz - 3 Questions

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

A [1, 2, 3]

B [2, 1, 3]

C [1, 3, 2]

D [3, 2, 1]

💡 Hint

Check the 'Current Array State' column at step 8 in execution_table

At which step does the first permutation get printed?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for 'Print' operation in execution_table

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

A Array stays changed, permutations will be incorrect

B Array resets automatically, no effect

C Only first permutation prints correctly

D Program crashes

💡 Hint

Refer to key_moments about why swapping back is needed and steps like 7 and 11

Concept Snapshot

Generate All Permutations of Array:
- Use recursion with a 'start' index
- Swap elements at 'start' with each index >= start
- Recurse with start+1
- Print when start == end
- Swap back after recursion to restore array
- This explores all possible orders of elements

Full Transcript

This concept shows how to generate all permutations of an array by swapping elements recursively. We start from the first index, swap it with itself and others, then recurse to fix the next index. When we reach the last index, we print the current array as a permutation. After each recursion, we swap back to restore the array for the next iteration. The execution table traces each swap, recursion, print, and backtrack step, showing how the array changes. Key moments clarify why swapping back is necessary and how recursion stops when the start index reaches the end. The visual quiz tests understanding of array states and recursion steps. This method ensures all permutations are generated without duplicates or missing any order.

Practice

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

easy

A. Finding the maximum element in the array

B. Sorting the array in ascending order

C. Listing all possible orders of the array elements

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 C

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
• Mixing permutations with finding max/min

2. Which of the following is the correct base case for a recursive function generating all permutations of an array arr of size n?

easy

A. if (start > n) { print(arr); return; }

B. if (start == n) { print(arr); return; }

C. if (n == 0) { return; }

D. if (start == 0) { print(arr); return; }

Solution

1. Step 1: Understand recursion base case

   The base case occurs when the start index reaches the array size, meaning a full permutation is formed.

2. Step 2: Match base case condition

   Condition start == n means all positions are fixed, so print the permutation and return.

3. Final Answer:

   if (start == n) { print(arr); return; } -> Option B

4. Quick Check:

   Base case when start equals array size [OK]

Hint: Base case: start index equals array length [OK]

Common Mistakes:

• Using start > n instead of start == n
• Printing when start == 0 (start of recursion)
• Missing base case leading to infinite recursion

3. What is 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++) printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        permute(arr, start + 1, n);
        temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
    }
}

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

medium

A. 1 2 \n 2 1 \n

B. 1 2 \n 1 2 \n

C. 2 1 \n 1 2 \n

D. No output

Solution

1. Step 1: Trace first call permute(arr, 0, 2)

   Start=0, loop i=0 to 1. Swap arr[0] with arr[0], call permute(arr,1,2).

2. Step 2: Trace second call permute(arr, 1, 2)

   Start=1, loop i=1 to 1. Swap arr[1] with arr[1], call permute(arr,2,2). Base case reached, print "1 2".

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

   Now arr = {2,1}. Call permute(arr,1,2) again, print "2 1".

4. Final Answer:

   1 2 2 1 -> Option A

5. Quick Check:

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

Hint: Swap and backtrack to generate permutations [OK]

Common Mistakes:

• Not swapping back after recursive call
• Printing incomplete permutations
• Confusing loop indices

4. Identify the error in the following code snippet that generates permutations of an array arr of size n:

void permute(int *arr, int start, int n) {
    if (start == n) {
        for (int i = 0; i < n; i++) printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        permute(arr, start + 1, n);
        // Missing swap back here
    }
}

medium

A. Missing swap back after recursive call causes incorrect permutations

B. Base case condition should be start > n

C. Loop should run from i = 0 to n

D. Printing inside base case is incorrect

Solution

1. Step 1: Understand swap and backtrack

   After swapping and recursive call, we must swap back to restore original array for next iteration.

2. Step 2: Identify missing swap back

   The comment shows swap back is missing, so array stays changed, causing wrong permutations.

3. Final Answer:

   Missing swap back after recursive call causes incorrect permutations -> Option A

4. Quick Check:

   Swap back needed to restore array [OK]

Hint: Always swap back after recursion to restore array [OK]

Common Mistakes:

• Forgetting to swap back after recursion
• Changing loop range incorrectly
• Wrong base case condition

5. Given an array arr = {1, 2, 2}, how many unique permutations will a correct algorithm generate that avoids duplicates?

hard

A. 6

B. 2

C. 4

D. 3

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

   Unique permutations are: [1,2,2], [2,1,2], [2,2,1]. But careful with counting duplicates in generation.

3. Step 3: Consider correct algorithm avoiding duplicates

   Some algorithms generate 4 permutations including one duplicate if not careful, but correct unique count is 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Unique permutations = 3 [OK]

Hint: Use factorial formula with duplicates: n!/k! [OK]

Common Mistakes:

• Counting duplicates as unique permutations
• Ignoring duplicate elements in calculation
• Assuming all permutations are unique