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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Permutation Generation

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

DSA Rust

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

fn main() {
    let mut nums = vec![1, 2];
    let mut result = Vec::new();
    permute(&mut nums, 0, &mut result);
    println!("{:?}", result);
}

A [[2, 1]]

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

C [[1, 2]]

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

💡 Hint

Think about how swapping elements and recursion generate all orderings.

The code swaps elements starting from the current index and recursively generates all permutations. For [1, 2], the permutations are [1, 2] and [2, 1].

🧠 Conceptual

intermediate

Number of Permutations for Array of Length 3

How many permutations are there for an array of length 3?

A 6

B 9

C 3

D 12

💡 Hint

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

For 3 elements, the number of permutations is 3! = 3 × 2 × 1 = 6.

🔧 Debug

advanced

Identify the Error in Permutation Code

What error does this Rust code produce when trying to generate permutations of [1, 2, 3]? fn permute(nums: &mut Vec, start: usize, result: &mut Vec>) { if start == nums.len() { result.push(nums.clone()); return; } for i in start..nums.len() { nums.swap(start, i); permute(nums, start + 1, result); } } fn main() { let mut nums = vec![1, 2, 3]; let mut result = Vec::new(); permute(&mut nums, 0, &mut result); println!("{:?}", result); }

A Missing swap to revert array state causing incorrect permutations

B Stack overflow due to infinite recursion

C Compilation error due to borrow checker

D No error, outputs all permutations correctly

💡 Hint

Check if the array is restored after recursive calls.

The code swaps elements before recursion but does not swap back after recursion, so the array state is not restored, leading to incorrect permutations.

🚀 Application

advanced

Permutations of Array with Duplicate Elements

Given the array [1, 1, 2], how many unique permutations are there?

A 6

B 3

C 2

D 4

💡 Hint

Consider that swapping identical elements does not create new unique permutations.

The total permutations of 3 elements is 3! = 6, but since two elements are identical, divide by 2! to get unique permutations: 6 / 2 = 3. However, the unique permutations are [1,1,2], [1,2,1], and [2,1,1], so 3 unique permutations.

❓ Predict Output

expert

Output of Permutation Generation with Early Return

What is the output of this Rust code that attempts to generate all permutations of [1, 2, 3] but returns early after the first permutation?

DSA Rust

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

fn main() {
    let mut nums = vec![1, 2, 3];
    let mut result = Vec::new();
    permute(&mut nums, 0, &mut result);
    println!("{:?}", result);
}

A [[1, 3, 2]]

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

C [[1, 2, 3]]

D []

💡 Hint

Look at the placement of the return statement inside the loop.

The return inside the loop causes the function to stop after the first recursive call, so only the first permutation [1, 2, 3] is generated.

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