Generate All Permutations of Array in DSA Rust - Build from Scratch

Generate All Permutations of Array

📖 Scenario: Imagine you have a set of unique numbers and you want to find every possible way to arrange them. This is useful in games, puzzles, and planning tasks where order matters.

🎯 Goal: You will build a Rust program that takes an array of numbers and generates all possible permutations of that array.

📋 What You'll Learn

Create an array with exact values [1, 2, 3]

Create a mutable vector to store permutations

Write a recursive function to generate permutations

Print all generated permutations

💡 Why This Matters

🌍 Real World

Generating permutations is useful in solving puzzles, arranging schedules, and exploring all possible options in games or decision-making.

💼 Career

Understanding recursion and permutations helps in algorithm design, coding interviews, and solving complex problems in software development.

1

Create the initial array

Create an array called nums with the exact values [1, 2, 3].

DSA Rust

# Create an array called nums with values [1, 2, 3]
# Your code here

Hint

Use let nums = [1, 2, 3]; to create the array.

2

Create a vector to store permutations

Create a mutable vector called result to store vectors of i32 that will hold all permutations.

DSA Rust

let nums = [1, 2, 3];
# Create a mutable vector called result to store permutations
# Your code here

Hint

Use let mut result: Vec> = Vec::new(); to create an empty vector of vectors.

3

Write the recursive function to generate permutations

Write a recursive function called permute that takes three parameters: a vector current of i32, a slice remaining of i32, and a mutable reference to result. The function should generate all permutations by adding elements from remaining to current and store complete permutations in result.

DSA Rust

let nums = [1, 2, 3];
let mut result: Vec> = Vec::new();

// Write the permute function here
# Your code here

Hint

Use recursion to build permutations by moving elements from remaining to current. When remaining is empty, add current to result.

4

Call the function and print all permutations

Call the permute function with an empty vector for current, the nums array as remaining, and a mutable reference to result. Then print each permutation in result on its own line.

DSA Rust

let nums = [1, 2, 3];
let mut result: Vec> = Vec::new();

fn permute(current: Vec, remaining: &[i32], result: &mut Vec>) {
    if remaining.is_empty() {
        result.push(current);
        return;
    }
    for i in 0..remaining.len() {
        let mut new_current = current.clone();
        new_current.push(remaining[i]);
        let mut new_remaining = Vec::from(&remaining[0..i]);
        new_remaining.extend_from_slice(&remaining[i+1..]);
        permute(new_current, &new_remaining, result);
    }
}

// Call permute and print all permutations
# Your code here

Hint

Call permute(Vec::new(), &nums, &mut result); then print each permutation with println!("{:?}", perm);.

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