Generate All Permutations of Array in DSA Rust

Mental Model

We want to list every possible order of the items in an array by swapping elements step-by-step.

Analogy: Imagine you have a set of colored balls in a row and you want to see every way to arrange them by swapping two balls at a time until all orders are shown.

Array: [1, 2, 3]
Positions: [0] [1] [2]
Start: 1 -> 2 -> 3

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements

Step 1: Start with index 0, swap element at 0 with 0 (no change), recurse to index 1

[1, 2, 3]

Why: Fix first element and generate permutations of the rest

Step 2: At index 1, swap element at 1 with 1 (no change), recurse to index 2

[1, 2, 3]

Why: Fix second element and generate permutations of the rest

Step 3: At index 2, reached end, record permutation [1, 2, 3]

[1, 2, 3]

Why: One complete permutation found

Step 4: Backtrack to index 1, swap element at 1 with 2, array becomes [1, 3, 2], recurse to index 2

[1, 3, 2]

Why: Try next element at position 1

Step 5: At index 2, reached end, record permutation [1, 3, 2]

[1, 3, 2]

Why: Another complete permutation found

Step 6: Backtrack to index 0, swap element at 0 with 1, array becomes [2, 1, 3], recurse to index 1

[2, 1, 3]

Why: Change first element to next option

Step 7: At index 1, swap element at 1 with 1 (no change), recurse to index 2

[2, 1, 3]

Why: Fix second element and generate permutations of the rest

Step 8: At index 2, reached end, record permutation [2, 1, 3]

[2, 1, 3]

Why: Complete permutation found

Result:

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

Annotated Code

DSA Rust

fn generate_permutations(arr: &mut Vec<i32>, start: usize, result: &mut Vec<Vec<i32>>) {
    if start == arr.len() {
        result.push(arr.clone()); // record current permutation
        return;
    }
    for i in start..arr.len() {
        arr.swap(start, i); // swap to fix element at start
        generate_permutations(arr, start + 1, result); // recurse for next position
        arr.swap(start, i); // backtrack to restore original order
    }
}

fn main() {
    let mut arr = vec![1, 2, 3];
    let mut result = Vec::new();
    generate_permutations(&mut arr, 0, &mut result);
    for perm in result {
        println!("{:?}", perm);
    }
}

if start == arr.len() {

check if all positions fixed -- base case to record permutation

result.push(arr.clone());

save current order as one permutation

for i in start..arr.len() {

try each element in current position

arr.swap(start, i);

fix element at start by swapping

generate_permutations(arr, start + 1, result);

recurse to fix next position

arr.swap(start, i);

backtrack to restore original order for next iteration

Output

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 2, 1]

[3, 1, 2]

Complexity Analysis

Time: O(n! * n) because there are n! permutations and each is copied of length n

Space: O(n! * n) to store all permutations plus O(n) recursion stack

vs Alternative: Naive approaches may generate duplicates or use extra data structures; this swaps in place and backtracks efficiently

Edge Cases

empty array

returns one permutation: empty list

DSA Rust

if start == arr.len() {

array with one element

returns one permutation: the array itself

DSA Rust

if start == arr.len() {

array with duplicate elements

generates permutations including duplicates; no filtering

DSA Rust

no specific guard; duplicates handled by swapping

When to Use This Pattern

When asked to list all possible orders of a set or array, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursion, causing incorrect array state in next iterations
Fix: Add a swap to backtrack after recursive call to restore original order

Mistake: Copying array too early or too late, missing some permutations
Fix: Copy array only when base case is reached (all positions fixed)

Summary

Generates all possible orders of an array by swapping elements and backtracking.

Use when you need every arrangement of elements without repetition.

The key is to fix one element at a time and swap back to explore all options.

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