Generate All Permutations of Array in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Rust

fn swap(arr: &mut Vec<i32>, i: usize, j: usize) {
    let temp = arr[[1]];
    arr[i] = arr[j];
    arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

Ai

B0

Cj

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i causes wrong element to be stored.

Using a fixed index like 0 or 1 does not swap the intended elements.

We store the element at index i in temp to swap it with element at index j.

2fill in blank

medium

Complete the code to generate permutations by recursion.

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() {
        swap(arr, start, [1]);
        permute(arr, start + 1, result);
        swap(arr, start, i);
    }
}

Drag options to blanks, or click blank then click option'

A0

Bstart

Ci

Darr.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with start instead of i does not change the array.

Using fixed indices causes incorrect permutations.

We swap the element at start with element at i to generate new permutations.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A==

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < or > causes infinite recursion or missing permutations.

Using <= causes out-of-bound errors.

The recursion stops when start equals the length of the array, meaning a full permutation is formed.

4fill in blank

hard

Fill both blanks to initialize the result vector and call the permutation function.

DSA Rust

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

Drag options to blanks, or click blank then click option'

AVec::new()

B0

C1

Dvec![]

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as start index misses permutations starting at 0.

Using vec![] instead of Vec::new() is valid but here Vec::new() is preferred.

We create an empty vector to store permutations and start recursion from index 0.

5fill in blank

hard

Fill all three blanks to complete the swap function, recursive call, and print statement.

DSA Rust

fn swap(arr: &mut Vec<i32>, i: usize, j: usize) {
    let temp = arr[[1]];
    arr[i] = arr[j];
    arr[j] = temp;
}

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() {
        swap(arr, start, i);
        permute(arr, start + 1, result);
        swap(arr, start, i);
    }
}

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

Drag options to blanks, or click blank then click option'

Ai

B0

Cresult

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong index in swap causes incorrect swapping.

Starting recursion at wrong index misses permutations.

Printing wrong variable shows incorrect output.

Swap uses i to store temp; recursion starts at 0; print the result vector.

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