Generate All Permutations of Array in DSA Rust - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with full array

↓

Choose element at index i

↓

Swap element i with element j

↓

Recurse with next index i+1

↓

If i == array length, record permutation

↓

Backtrack: swap back elements i and j

Back to choose next j↓

Repeat until all permutations generated

↩Back to choose next j

We pick each element in turn, swap it to the current position, recurse to fix the next position, and backtrack by swapping back to explore all permutations.

Execution Sample

DSA Rust

fn permute(arr: &mut Vec<i32>, start: usize, result: &mut Vec<Vec<i32>>) {
    if start == arr.len() {
        result.push(arr.clone());
        return;
    }
    for i in start..arr.len() {
        arr.swap(start, i);
        permute(arr, start + 1, result);
        arr.swap(start, i);
    }
}

This function generates all permutations of the array by swapping elements starting from index 'start' and recursing.

Execution Table

Step	Operation	Current Index (start)	Swapped Indices	Permutation Recorded	Array State
1	Start recursion	0	-	No	[1, 2, 3]
2	Swap start=0 with i=0	0	(0,0)	No	[1, 2, 3]
3	Recurse with start=1	1	-	No	[1, 2, 3]
4	Swap start=1 with i=1	1	(1,1)	No	[1, 2, 3]
5	Recurse with start=2	2	-	No	[1, 2, 3]
6	Swap start=2 with i=2	2	(2,2)	No	[1, 2, 3]
7	Recurse with start=3	3	-	Yes	[1, 2, 3]
8	Backtrack swap start=2 with i=2	2	(2,2)	No	[1, 2, 3]
9	Backtrack swap start=1 with i=1	1	(1,1)	No	[1, 2, 3]
10	Swap start=1 with i=2	1	(1,2)	No	[1, 3, 2]
11	Recurse with start=2	2	-	No	[1, 3, 2]
12	Swap start=2 with i=2	2	(2,2)	No	[1, 3, 2]
13	Recurse with start=3	3	-	Yes	[1, 3, 2]
14	Backtrack swap start=2 with i=2	2	(2,2)	No	[1, 3, 2]
15	Backtrack swap start=1 with i=2	1	(1,2)	No	[1, 2, 3]
16	Backtrack swap start=0 with i=0	0	(0,0)	No	[1, 2, 3]
17	Swap start=0 with i=1	0	(0,1)	No	[2, 1, 3]
18	Recurse with start=1	1	-	No	[2, 1, 3]
19	Swap start=1 with i=1	1	(1,1)	No	[2, 1, 3]
20	Recurse with start=2	2	-	No	[2, 1, 3]
21	Swap start=2 with i=2	2	(2,2)	No	[2, 1, 3]
22	Recurse with start=3	3	-	Yes	[2, 1, 3]
23	Backtrack swap start=2 with i=2	2	(2,2)	No	[2, 1, 3]
24	Backtrack swap start=1 with i=1	1	(1,1)	No	[2, 1, 3]
25	Swap start=1 with i=2	1	(1,2)	No	[2, 3, 1]
26	Recurse with start=2	2	-	No	[2, 3, 1]
27	Swap start=2 with i=2	2	(2,2)	No	[2, 3, 1]
28	Recurse with start=3	3	-	Yes	[2, 3, 1]
29	Backtrack swap start=2 with i=2	2	(2,2)	No	[2, 3, 1]
30	Backtrack swap start=1 with i=2	1	(1,2)	No	[2, 1, 3]
31	Backtrack swap start=0 with i=1	0	(0,1)	No	[1, 2, 3]
32	Swap start=0 with i=2	0	(0,2)	No	[3, 2, 1]
33	Recurse with start=1	1	-	No	[3, 2, 1]
34	Swap start=1 with i=1	1	(1,1)	No	[3, 2, 1]
35	Recurse with start=2	2	-	No	[3, 2, 1]
36	Swap start=2 with i=2	2	(2,2)	No	[3, 2, 1]
37	Recurse with start=3	3	-	Yes	[3, 2, 1]
38	Backtrack swap start=2 with i=2	2	(2,2)	No	[3, 2, 1]
39	Backtrack swap start=1 with i=1	1	(1,1)	No	[3, 2, 1]
40	Swap start=1 with i=2	1	(1,2)	No	[3, 1, 2]
41	Recurse with start=2	2	-	No	[3, 1, 2]
42	Swap start=2 with i=2	2	(2,2)	No	[3, 1, 2]
43	Recurse with start=3	3	-	Yes	[3, 1, 2]
44	Backtrack swap start=2 with i=2	2	(2,2)	No	[3, 1, 2]
45	Backtrack swap start=1 with i=2	1	(1,2)	No	[3, 2, 1]
46	Backtrack swap start=0 with i=2	0	(0,2)	No	[1, 2, 3]
47	End recursion	-	-	All permutations recorded	[1, 2, 3]

💡 Recursion ends when start index reaches array length, all permutations recorded.

Variable Tracker

Variable	Start	After Step 2	After Step 10	After Step 17	After Step 25	After Step 32	Final
start	0	0	1	1	1	1	3
arr	[1,2,3]	[1,2,3]	[1,3,2]	[2,1,3]	[2,3,1]	[3,2,1]	[1,2,3]
result (count)	0	0	2	3	5	6	6

Key Moments - 3 Insights

Why do we swap elements back after recursion?

Swapping back restores the array to its previous state so that other permutations can be generated correctly, as shown in steps 8, 14, 15, etc. Without backtracking, the array would remain changed and permutations would be incorrect.

When do we record a permutation?

A permutation is recorded when the 'start' index reaches the array length, meaning all positions are fixed. This happens at steps 7, 13, 22, 28, 37, and 43.

Why do we swap the element at 'start' with itself sometimes?

Swapping an element with itself (like at step 2) is necessary to include the current element in the permutation and to keep the logic uniform. It ensures the element at 'start' is considered fixed before recursing.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state at step 10?

A [2, 1, 3]

B [1, 2, 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 is the first permutation recorded?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for the first 'Yes' in the 'Permutation Recorded' column in execution_table.

If we skip swapping back after recursion, what will happen?

A Permutations will be incorrect or repeated

B All permutations will still be correct

C Only one permutation will be recorded

D The program will crash

💡 Hint

Refer to key_moments explanation about backtracking swaps.

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.
- When start == array length, record permutation.
- Backtrack by swapping back to restore array.
- Ensures all permutations generated without duplicates.

Full Transcript

This visualization shows how to generate all permutations of an array by swapping elements starting from a 'start' index. At each step, the element at 'start' is swapped with elements at or after 'start', then the function recurses to fix the next position. When the 'start' index reaches the array length, a complete permutation is recorded. After recursion, the elements are swapped back to restore the original order, allowing exploration of other permutations. The execution table tracks each swap, recursion, and backtrack step, showing the array state and when permutations are recorded. Key moments clarify why backtracking is needed and when permutations are saved. The visual quiz tests understanding of array states and recursion steps. This method ensures all permutations are generated systematically and correctly.

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. Removing duplicate elements from the array

D. Finding the maximum element in 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 element

2. Which Rust code snippet correctly starts generating permutations of a vector vec![1, 2, 3] using recursion?

easy

A. fn permute(arr: &mut Vec<i32>, start: usize) { if start == arr.len() { println!("{:?}", arr); } else { for i in start..arr.len() { arr.swap(start, i); permute(arr, start + 1); arr.swap(start, i); } } }

B. fn permute(arr: Vec<i32>) { for i in 0..arr.len() { println!("{:?}", arr[i]); } }

C. fn permute(arr: &Vec<i32>) { println!("{:?}", arr); }

D. fn permute(arr: &mut Vec<i32>) { arr.sort(); println!("{:?}", arr); }

Solution

1. Step 1: Identify recursive permutation logic

   fn permute(arr: &mut Vec<i32>, start: usize) { if start == arr.len() { println!("{:?}", arr); } else { for i in start..arr.len() { arr.swap(start, i); permute(arr, start + 1); arr.swap(start, i); } } } uses recursion with swapping and backtracking to generate permutations.

2. Step 2: Check other options

   Options B, C, and D do not generate permutations; they only print or sort.

3. Final Answer:

   fn permute(arr: &mut Vec<i32>, start: usize) { if start == arr.len() { println!("{:?}", arr); } else { for i in start..arr.len() { arr.swap(start, i); permute(arr, start + 1); arr.swap(start, i); } } } -> Option A

4. Quick Check:

   Recursive swap + backtrack = fn permute(arr: &mut Vec<i32>, start: usize) { if start == arr.len() { println!("{:?}", arr); } else { for i in start..arr.len() { arr.swap(start, i); permute(arr, start + 1); arr.swap(start, i); } } } [OK]

Hint: Look for recursion with swap and backtrack [OK]

Common Mistakes:

• Not using mutable reference for swapping
• Missing recursive call
• Printing elements instead of permutations

3. What is the output of this Rust code snippet?

fn permute(arr: &mut Vec<i32>, start: usize) {
    if start == arr.len() {
        println!("{:?}", arr);
    } else {
        for i in start..arr.len() {
            arr.swap(start, i);
            permute(arr, start + 1);
            arr.swap(start, i);
        }
    }
}

fn main() {
    let mut v = vec![1, 2];
    permute(&mut v, 0);
}

medium

A. [1, 2]

B. [1, 2]
[2, 1]

C. [2, 1]

D. Compilation error

Solution

1. Step 1: Trace recursive calls for vec![1, 2]

   Start at index 0, swap with 0 and 1: - Swap(0,0): [1,2], print when start=2 - Swap(0,1): [2,1], print when start=2

2. Step 2: Confirm output lines

   Both permutations [1, 2] and [2, 1] are printed in order.

3. Final Answer:

   [1, 2] [2, 1] -> Option B

4. Quick Check:

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

Hint: Small array permutations = factorial length outputs [OK]

Common Mistakes:

• Expecting only one permutation output
• Confusing swap order
• Assuming compilation error

4. Identify the bug in this Rust code for generating permutations and select the fix:

fn permute(arr: Vec<i32>, start: usize) {
    if start == arr.len() {
        println!("{:?}", arr);
    } else {
        for i in start..arr.len() {
            let mut arr = arr.clone();
            arr.swap(start, i);
            permute(arr, start + 1);
        }
    }
}

fn main() {
    let v = vec![1, 2, 3];
    permute(v, 0);
}

medium

A. No bug, code works fine

B. Add mut keyword to v in main

C. Replace arr.swap with arr.reverse

D. Change parameter to mutable reference: arr: &mut Vec<i32> and remove cloning

Solution

1. Step 1: Analyze cloning and mutation

   Cloning arr each loop causes performance issues and unnecessary copies.

2. Step 2: Fix by using mutable reference

   Passing &mut Vec<i32> allows swapping in place and backtracking without cloning.

3. Final Answer:

   Change parameter to mutable reference: arr: &mut Vec<i32> and remove cloning -> Option D

4. Quick Check:

   Use mutable reference to avoid cloning [OK]

Hint: Use &mut Vec to swap without cloning [OK]

Common Mistakes:

• Cloning inside loop causes inefficiency
• Not using mutable reference for swaps
• Thinking adding mut to main vector fixes logic

5. Given a vector vec![1, 2, 2], how many unique permutations will the standard recursive swap method print without filtering duplicates?

hard

A. 2

B. 3

C. 6

D. 1

Solution

1. Step 1: Calculate total permutations without filtering

   For 3 elements, total permutations = 3! = 6.

2. Step 2: Consider duplicates in array

   Standard recursive swap method does not filter duplicates, so all 6 permutations including duplicates print.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   3! = 6 permutations printed [OK]

Hint: Without filtering, duplicates cause factorial count [OK]

Common Mistakes:

• Assuming duplicates reduce output automatically
• Confusing unique permutations with total permutations
• Thinking output is 3 or 2 without filtering