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

//! 1064: Generate All Permutations via Backtracking.
//!
//! Three approaches translated from the OCaml source:
//!
//! 1. [`permutations_swap`] — in-place swap-based backtracking.
//! 2. [`permutations_insert`] — purely functional list insertion.
//! 3. [`permutations_flags`] — backtracking guided by a `used` flag array.

/// Generate all permutations via swap-based backtracking.
///
/// The input slice is cloned into a working buffer, so the caller's data is
/// untouched. Order of results matches the OCaml reference implementation
/// (reversed accumulator).
pub fn permutations_swap<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn permute<T: Clone>(start: usize, buf: &mut [T], results: &mut Vec<Vec<T>>) {
        if start == buf.len() {
            results.push(buf.to_vec());
            return;
        }
        for i in start..buf.len() {
            buf.swap(start, i);
            permute(start + 1, buf, results);
            buf.swap(start, i);
        }
    }

    let mut buf: Vec<T> = items.to_vec();
    let mut results = Vec::new();
    permute(0, &mut buf, &mut results);
    results
}

/// Insert `x` at every possible position of `tail`, returning all resulting
/// lists. Mirrors the OCaml `insert` helper used by [`permutations_insert`].
fn insert_everywhere<T: Clone>(x: &T, tail: &[T]) -> Vec<Vec<T>> {
    if tail.is_empty() {
        return vec![vec![x.clone()]];
    }
    let mut out = Vec::new();
    let mut head = Vec::with_capacity(tail.len() + 1);
    head.push(x.clone());
    head.extend_from_slice(tail);
    out.push(head);
    for rest in insert_everywhere(x, &tail[1..]) {
        let mut combined = Vec::with_capacity(rest.len() + 1);
        combined.push(tail[0].clone());
        combined.extend(rest);
        out.push(combined);
    }
    out
}

/// Generate all permutations by recursively inserting each element into every
/// position of the permutations of the remaining elements.
pub fn permutations_insert<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    if items.is_empty() {
        return vec![Vec::new()];
    }
    let rest = permutations_insert(&items[1..]);
    let head = &items[0];
    rest.into_iter()
        .flat_map(|perm| insert_everywhere(head, &perm))
        .collect()
}

/// Generate all permutations using a `used` flag array to track which elements
/// have been placed in the current candidate.
pub fn permutations_flags<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn build<T: Clone>(
        items: &[T],
        used: &mut [bool],
        current: &mut Vec<T>,
        results: &mut Vec<Vec<T>>,
    ) {
        if current.len() == items.len() {
            results.push(current.clone());
            return;
        }
        for i in 0..items.len() {
            if !used[i] {
                used[i] = true;
                current.push(items[i].clone());
                build(items, used, current, results);
                current.pop();
                used[i] = false;
            }
        }
    }

    let mut used = vec![false; items.len()];
    let mut current = Vec::with_capacity(items.len());
    let mut results = Vec::new();
    build(items, &mut used, &mut current, &mut results);
    results
}

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

    fn factorial(n: usize) -> usize {
        (1..=n).product::<usize>().max(1)
    }

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

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

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

    #[test]
    fn empty_input_yields_single_empty_permutation() {
        let perms: Vec<Vec<i32>> = permutations_insert(&[]);
        assert_eq!(perms, vec![Vec::<i32>::new()]);
        assert_eq!(permutations_flags::<i32>(&[]).len(), 1);
        assert_eq!(permutations_swap::<i32>(&[]).len(), 1);
    }

    #[test]
    fn single_element_yields_one_permutation() {
        assert_eq!(permutations_insert(&[42]), vec![vec![42]]);
        assert_eq!(permutations_flags(&[42]), vec![vec![42]]);
        assert_eq!(permutations_swap(&[42]), vec![vec![42]]);
    }

    #[test]
    fn all_three_approaches_agree_as_sets() {
        let input = [1, 2, 3, 4];
        let mut a = permutations_swap(&input);
        let mut b = permutations_insert(&input);
        let mut c = permutations_flags(&input);
        for list in [&mut a, &mut b, &mut c] {
            list.sort();
        }
        assert_eq!(a, b);
        assert_eq!(b, c);
        assert_eq!(a.len(), factorial(input.len()));
    }

    #[test]
    fn works_with_non_integer_types() {
        let perms = permutations_flags(&["x", "y", "z"]);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec!["x", "y", "z"]));
        assert!(perms.contains(&vec!["z", "y", "x"]));
    }
}

(* 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

//! 1064: Generate All Permutations via Backtracking.
//!
//! Three approaches translated from the OCaml source:
//!
//! 1. [`permutations_swap`] — in-place swap-based backtracking.
//! 2. [`permutations_insert`] — purely functional list insertion.
//! 3. [`permutations_flags`] — backtracking guided by a `used` flag array.

/// Generate all permutations via swap-based backtracking.
///
/// The input slice is cloned into a working buffer, so the caller's data is
/// untouched. Order of results matches the OCaml reference implementation
/// (reversed accumulator).
pub fn permutations_swap<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn permute<T: Clone>(start: usize, buf: &mut [T], results: &mut Vec<Vec<T>>) {
        if start == buf.len() {
            results.push(buf.to_vec());
            return;
        }
        for i in start..buf.len() {
            buf.swap(start, i);
            permute(start + 1, buf, results);
            buf.swap(start, i);
        }
    }

    let mut buf: Vec<T> = items.to_vec();
    let mut results = Vec::new();
    permute(0, &mut buf, &mut results);
    results
}

/// Insert `x` at every possible position of `tail`, returning all resulting
/// lists. Mirrors the OCaml `insert` helper used by [`permutations_insert`].
fn insert_everywhere<T: Clone>(x: &T, tail: &[T]) -> Vec<Vec<T>> {
    if tail.is_empty() {
        return vec![vec![x.clone()]];
    }
    let mut out = Vec::new();
    let mut head = Vec::with_capacity(tail.len() + 1);
    head.push(x.clone());
    head.extend_from_slice(tail);
    out.push(head);
    for rest in insert_everywhere(x, &tail[1..]) {
        let mut combined = Vec::with_capacity(rest.len() + 1);
        combined.push(tail[0].clone());
        combined.extend(rest);
        out.push(combined);
    }
    out
}

/// Generate all permutations by recursively inserting each element into every
/// position of the permutations of the remaining elements.
pub fn permutations_insert<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    if items.is_empty() {
        return vec![Vec::new()];
    }
    let rest = permutations_insert(&items[1..]);
    let head = &items[0];
    rest.into_iter()
        .flat_map(|perm| insert_everywhere(head, &perm))
        .collect()
}

/// Generate all permutations using a `used` flag array to track which elements
/// have been placed in the current candidate.
pub fn permutations_flags<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn build<T: Clone>(
        items: &[T],
        used: &mut [bool],
        current: &mut Vec<T>,
        results: &mut Vec<Vec<T>>,
    ) {
        if current.len() == items.len() {
            results.push(current.clone());
            return;
        }
        for i in 0..items.len() {
            if !used[i] {
                used[i] = true;
                current.push(items[i].clone());
                build(items, used, current, results);
                current.pop();
                used[i] = false;
            }
        }
    }

    let mut used = vec![false; items.len()];
    let mut current = Vec::with_capacity(items.len());
    let mut results = Vec::new();
    build(items, &mut used, &mut current, &mut results);
    results
}

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

    fn factorial(n: usize) -> usize {
        (1..=n).product::<usize>().max(1)
    }

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

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

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

    #[test]
    fn empty_input_yields_single_empty_permutation() {
        let perms: Vec<Vec<i32>> = permutations_insert(&[]);
        assert_eq!(perms, vec![Vec::<i32>::new()]);
        assert_eq!(permutations_flags::<i32>(&[]).len(), 1);
        assert_eq!(permutations_swap::<i32>(&[]).len(), 1);
    }

    #[test]
    fn single_element_yields_one_permutation() {
        assert_eq!(permutations_insert(&[42]), vec![vec![42]]);
        assert_eq!(permutations_flags(&[42]), vec![vec![42]]);
        assert_eq!(permutations_swap(&[42]), vec![vec![42]]);
    }

    #[test]
    fn all_three_approaches_agree_as_sets() {
        let input = [1, 2, 3, 4];
        let mut a = permutations_swap(&input);
        let mut b = permutations_insert(&input);
        let mut c = permutations_flags(&input);
        for list in [&mut a, &mut b, &mut c] {
            list.sort();
        }
        assert_eq!(a, b);
        assert_eq!(b, c);
        assert_eq!(a.len(), factorial(input.len()));
    }

    #[test]
    fn works_with_non_integer_types() {
        let perms = permutations_flags(&["x", "y", "z"]);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec!["x", "y", "z"]));
        assert!(perms.contains(&vec!["z", "y", "x"]));
    }
}

(* 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::*;

    fn factorial(n: usize) -> usize {
        (1..=n).product::<usize>().max(1)
    }

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

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

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

    #[test]
    fn empty_input_yields_single_empty_permutation() {
        let perms: Vec<Vec<i32>> = permutations_insert(&[]);
        assert_eq!(perms, vec![Vec::<i32>::new()]);
        assert_eq!(permutations_flags::<i32>(&[]).len(), 1);
        assert_eq!(permutations_swap::<i32>(&[]).len(), 1);
    }

    #[test]
    fn single_element_yields_one_permutation() {
        assert_eq!(permutations_insert(&[42]), vec![vec![42]]);
        assert_eq!(permutations_flags(&[42]), vec![vec![42]]);
        assert_eq!(permutations_swap(&[42]), vec![vec![42]]);
    }

    #[test]
    fn all_three_approaches_agree_as_sets() {
        let input = [1, 2, 3, 4];
        let mut a = permutations_swap(&input);
        let mut b = permutations_insert(&input);
        let mut c = permutations_flags(&input);
        for list in [&mut a, &mut b, &mut c] {
            list.sort();
        }
        assert_eq!(a, b);
        assert_eq!(b, c);
        assert_eq!(a.len(), factorial(input.len()));
    }

    #[test]
    fn works_with_non_integer_types() {
        let perms = permutations_flags(&["x", "y", "z"]);
        assert_eq!(perms.len(), 6);
        assert!(perms.contains(&vec!["x", "y", "z"]));
        assert!(perms.contains(&vec!["z", "y", "x"]));
    }
}

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