1064 Intermediate

1064-permutations — Generate All Permutations

Functional Programming

Tutorial

The Problem

Generating all permutations of a sequence is essential for brute-force combinatorial search: testing all orderings of tasks for a scheduling problem, generating all possible moves in game AI, and exhaustive testing of commutative operations. There are n! permutations of n elements.

Two classic algorithms: the swap-based approach (Heap's algorithm variant) and the selection approach using a "used" flags array. Both produce all n! permutations but in different orders.

🎯 Learning Outcomes

• Implement permutation generation via swap-based backtracking

• Implement permutation generation via selection with a used-flags array

• Compare the two approaches for their properties (lexicographic order, allocation patterns)

• Handle duplicates by sorting and skipping repeated elements

• Generate permutations lazily using iterators

Code Example

#![allow(clippy::all)]
// 1064: Generate All Permutations via Backtracking

// Approach 1: Swap-based backtracking
fn permutations_swap(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    fn permute(start: usize, nums: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        if start == nums.len() {
            results.push(nums.clone());
            return;
        }
        for i in start..nums.len() {
            nums.swap(start, i);
            permute(start + 1, nums, results);
            nums.swap(start, i);
        }
    }
    permute(0, nums, &mut results);
    results
}

// Approach 2: Used-flags approach
fn permutations_flags(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut results = Vec::new();
    let mut used = vec![false; n];
    let mut current = Vec::with_capacity(n);

    fn build(
        nums: &[i32],
        used: &mut Vec<bool>,
        current: &mut Vec<i32>,
        results: &mut Vec<Vec<i32>>,
    ) {
        if current.len() == nums.len() {
            results.push(current.clone());
            return;
        }
        for i in 0..nums.len() {
            if !used[i] {
                used[i] = true;
                current.push(nums[i]);
                build(nums, used, current, results);
                current.pop();
                used[i] = false;
            }
        }
    }

    build(nums, &mut used, &mut current, &mut results);
    results
}

// Approach 3: Iterator-based using Heap's algorithm
fn permutations_heap(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut arr = nums.to_vec();
    let n = arr.len();
    let mut results = vec![arr.clone()];
    let mut c = vec![0usize; n];
    let mut i = 0;
    while i < n {
        if c[i] < i {
            if i % 2 == 0 {
                arr.swap(0, i);
            } else {
                arr.swap(c[i], i);
            }
            results.push(arr.clone());
            c[i] += 1;
            i = 0;
        } else {
            c[i] = 0;
            i += 1;
        }
    }
    results
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_swap() {
        let mut nums = vec![1, 2, 3];
        let perms = permutations_swap(&mut nums);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec![1, 2, 3]));
        assert!(perms.contains(&vec![3, 2, 1]));
    }

    #[test]
    fn test_flags() {
        let perms = permutations_flags(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_heap() {
        let perms = permutations_heap(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_single() {
        assert_eq!(permutations_flags(&[42]).len(), 1);
    }
}

(* 1064: Generate All Permutations via Backtracking *)

(* Approach 1: Swap-based backtracking *)
let permutations_swap arr =
  let n = Array.length arr in
  let results = ref [] in
  let rec permute start =
    if start = n then
      results := Array.to_list arr :: !results
    else
      for i = start to n - 1 do
        let tmp = arr.(start) in
        arr.(start) <- arr.(i);
        arr.(i) <- tmp;
        permute (start + 1);
        let tmp = arr.(start) in
        arr.(start) <- arr.(i);
        arr.(i) <- tmp
      done
  in
  permute 0;
  List.rev !results

(* Approach 2: Functional with list insertion *)
let permutations_insert lst =
  let rec insert x = function
    | [] -> [[x]]
    | hd :: tl as l ->
      (x :: l) :: List.map (fun rest -> hd :: rest) (insert x tl)
  in
  let rec perms = function
    | [] -> [[]]
    | hd :: tl ->
      List.concat_map (insert hd) (perms tl)
  in
  perms lst

(* Approach 3: Using used-flags *)
let permutations_flags lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let used = Array.make n false in
  let results = ref [] in
  let current = Array.make n 0 in
  let rec build pos =
    if pos = n then
      results := Array.to_list current :: !results
    else
      for i = 0 to n - 1 do
        if not used.(i) then begin
          used.(i) <- true;
          current.(pos) <- arr.(i);
          build (pos + 1);
          used.(i) <- false
        end
      done
  in
  build 0;
  List.rev !results

let () =
  let perms1 = permutations_swap [|1; 2; 3|] in
  assert (List.length perms1 = 6);
  assert (List.mem [1; 2; 3] perms1);
  assert (List.mem [3; 2; 1] perms1);

  let perms2 = permutations_insert [1; 2; 3] in
  assert (List.length perms2 = 6);

  let perms3 = permutations_flags [1; 2; 3] in
  assert (List.length perms3 = 6);

  (* Single element *)
  assert (List.length (permutations_insert [42]) = 1);

  Printf.printf "✓ All tests passed\n"

Key Differences

Swap vs copy: Rust's swap-based version modifies the input array in place; OCaml's selection approach builds into a separate current array.

Lexicographic order: The selection/flags approach produces permutations in lexicographic order when the input is sorted; swap-based does not.

Memory allocation: Both collect all n! permutations, allocating O(n × n!) memory total. Lazy permutation generation (via iterators) avoids this.

**itertools::permutations**: The itertools crate provides iter.permutations(k) for lazy k-permutations in Rust; OCaml's Base.List has no direct equivalent.

OCaml Approach

let permutations lst =
  let n = List.length lst in
  let arr = Array.of_list lst in
  let results = ref [] in
  let used = Array.make n false in
  let current = Array.make n 0 in
  let rec build len =
    if len = n then results := Array.to_list current :: !results
    else
      for i = 0 to n - 1 do
        if not used.(i) then begin
          current.(len) <- arr.(i);
          used.(i) <- true;
          build (len + 1);
          used.(i) <- false
        end
      done
  in
  build 0;
  !results

Structurally identical. OCaml's mutable arrays and refs replace Rust's explicit &mut parameters.

Full Source

#![allow(clippy::all)]
// 1064: Generate All Permutations via Backtracking

// Approach 1: Swap-based backtracking
fn permutations_swap(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    fn permute(start: usize, nums: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        if start == nums.len() {
            results.push(nums.clone());
            return;
        }
        for i in start..nums.len() {
            nums.swap(start, i);
            permute(start + 1, nums, results);
            nums.swap(start, i);
        }
    }
    permute(0, nums, &mut results);
    results
}

// Approach 2: Used-flags approach
fn permutations_flags(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut results = Vec::new();
    let mut used = vec![false; n];
    let mut current = Vec::with_capacity(n);

    fn build(
        nums: &[i32],
        used: &mut Vec<bool>,
        current: &mut Vec<i32>,
        results: &mut Vec<Vec<i32>>,
    ) {
        if current.len() == nums.len() {
            results.push(current.clone());
            return;
        }
        for i in 0..nums.len() {
            if !used[i] {
                used[i] = true;
                current.push(nums[i]);
                build(nums, used, current, results);
                current.pop();
                used[i] = false;
            }
        }
    }

    build(nums, &mut used, &mut current, &mut results);
    results
}

// Approach 3: Iterator-based using Heap's algorithm
fn permutations_heap(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut arr = nums.to_vec();
    let n = arr.len();
    let mut results = vec![arr.clone()];
    let mut c = vec![0usize; n];
    let mut i = 0;
    while i < n {
        if c[i] < i {
            if i % 2 == 0 {
                arr.swap(0, i);
            } else {
                arr.swap(c[i], i);
            }
            results.push(arr.clone());
            c[i] += 1;
            i = 0;
        } else {
            c[i] = 0;
            i += 1;
        }
    }
    results
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_swap() {
        let mut nums = vec![1, 2, 3];
        let perms = permutations_swap(&mut nums);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec![1, 2, 3]));
        assert!(perms.contains(&vec![3, 2, 1]));
    }

    #[test]
    fn test_flags() {
        let perms = permutations_flags(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_heap() {
        let perms = permutations_heap(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_single() {
        assert_eq!(permutations_flags(&[42]).len(), 1);
    }
}

(* 1064: Generate All Permutations via Backtracking *)

(* Approach 1: Swap-based backtracking *)
let permutations_swap arr =
  let n = Array.length arr in
  let results = ref [] in
  let rec permute start =
    if start = n then
      results := Array.to_list arr :: !results
    else
      for i = start to n - 1 do
        let tmp = arr.(start) in
        arr.(start) <- arr.(i);
        arr.(i) <- tmp;
        permute (start + 1);
        let tmp = arr.(start) in
        arr.(start) <- arr.(i);
        arr.(i) <- tmp
      done
  in
  permute 0;
  List.rev !results

(* Approach 2: Functional with list insertion *)
let permutations_insert lst =
  let rec insert x = function
    | [] -> [[x]]
    | hd :: tl as l ->
      (x :: l) :: List.map (fun rest -> hd :: rest) (insert x tl)
  in
  let rec perms = function
    | [] -> [[]]
    | hd :: tl ->
      List.concat_map (insert hd) (perms tl)
  in
  perms lst

(* Approach 3: Using used-flags *)
let permutations_flags lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let used = Array.make n false in
  let results = ref [] in
  let current = Array.make n 0 in
  let rec build pos =
    if pos = n then
      results := Array.to_list current :: !results
    else
      for i = 0 to n - 1 do
        if not used.(i) then begin
          used.(i) <- true;
          current.(pos) <- arr.(i);
          build (pos + 1);
          used.(i) <- false
        end
      done
  in
  build 0;
  List.rev !results

let () =
  let perms1 = permutations_swap [|1; 2; 3|] in
  assert (List.length perms1 = 6);
  assert (List.mem [1; 2; 3] perms1);
  assert (List.mem [3; 2; 1] perms1);

  let perms2 = permutations_insert [1; 2; 3] in
  assert (List.length perms2 = 6);

  let perms3 = permutations_flags [1; 2; 3] in
  assert (List.length perms3 = 6);

  (* Single element *)
  assert (List.length (permutations_insert [42]) = 1);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_swap() {
        let mut nums = vec![1, 2, 3];
        let perms = permutations_swap(&mut nums);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec![1, 2, 3]));
        assert!(perms.contains(&vec![3, 2, 1]));
    }

    #[test]
    fn test_flags() {
        let perms = permutations_flags(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_heap() {
        let perms = permutations_heap(&[1, 2, 3]);
        assert_eq!(perms.len(), 6);
    }

    #[test]
    fn test_single() {
        assert_eq!(permutations_flags(&[42]).len(), 1);
    }
}

Deep Comparison

Permutations — Comparison

Core Insight

Three classic approaches: swap-based (in-place), used-flags (separate buffer), and insertion-based (purely functional in OCaml) / Heap's algorithm (iterative in Rust). Each trades off between elegance and efficiency.

OCaml Approach

• Swap-based: Array with index swapping

• Insertion-based: purely functional with List.concat_map — most idiomatic OCaml

• Used-flags: imperative with boolean array

• List.rev to maintain order

Rust Approach

• Swap-based: Vec::swap() — clean and idiomatic

• Used-flags: Vec<bool> with push/pop on current

• Heap's algorithm: iterative, one swap per permutation — most efficient

• clone() needed to snapshot each permutation

Comparison Table

Aspect	OCaml	Rust
Swap	`let tmp = ...; ... <- ...` (manual)	`Vec::swap(i, j)` (built-in)
Functional style	`List.concat_map` + insertion	Not natural (would need `im` crate)
Heap's algorithm	Not shown	Iterative with `c` array
Snapshot	`Array.to_list`	`.clone()`
Space	O(n!) results + O(n) stack	O(n!) results + O(n) stack

Exercises

Implement permutations_lazy(nums: Vec<i32>) -> impl Iterator<Item=Vec<i32>> using Heap's algorithm as a lazy iterator.

Write permutations_unique(nums: &mut [i32]) -> Vec<Vec<i32>> that handles duplicate elements by sorting and skipping repeated swaps.

Implement nth_permutation(nums: &[i32], n: usize) -> Vec<i32> that generates only the nth permutation in lexicographic order using factoradic number representation.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust