025 — Generate a Random Permutation of the Elements of a List
Tutorial Video
Text description (accessibility)
This video demonstrates the "025 — Generate a Random Permutation of the Elements of a List" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. A random permutation (shuffle) rearranges all elements of a list with each of the n! Key difference from OCaml: 1. **`shuffle` in stdlib**: Rust's `SliceRandom::shuffle` is in the `rand` crate (not stdlib). OCaml has no standard `shuffle`; you implement it manually.
Tutorial
The Problem
A random permutation (shuffle) rearranges all elements of a list with each of the n! arrangements equally likely. This is different from random selection: a permutation includes every element exactly once, just in a random order. The canonical algorithm is Fisher-Yates (Knuth) shuffle, which runs in O(n) time and is proven to produce a uniform distribution.
Random permutations appear in card shuffling, game AI (random move ordering in minimax), neural network weight initialization (shuffle before SGD), randomized QuickSort (shuffle before partitioning), and combinatorics testing (generate test cases). Non-uniform shuffles (like naively sorting with random comparators) are a well-known source of bias bugs.
🎯 Learning Outcomes
Vec::shuffle from rand::seq::SliceRandom for uniform random permutationVec::shuffle(&mut rng) from rand::seq::SliceRandom for uniform random permutationCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
shuffle in stdlib**: Rust's SliceRandom::shuffle is in the rand crate (not stdlib). OCaml has no standard shuffle; you implement it manually.Array.of_list. Rust starts with Vec.&mut v). OCaml mutates the array in place with arr.(i) <- ....random_select applied to the full list — selecting all n elements produces a permutation, but this is O(n²) naive vs O(n) Fisher-Yates.Vec supports this natively. OCaml must convert to Array first, then back to List — two O(n) conversions.SliceRandom trait:** Rust's .shuffle(&mut rng) is provided by the rand crate via rand::seq::SliceRandom. No equivalent in OCaml's stdlib.OCaml Approach
OCaml's implementation uses the same algorithm with arrays: let permutation lst = let arr = Array.of_list lst in let n = Array.length arr in for i = n - 1 downto 1 do let j = Random.int (i + 1) in let tmp = arr.(i) in arr.(i) <- arr.(j); arr.(j) <- tmp done; Array.to_list arr. Alternatively: compose range(1, n) and random_select(lst, n) — select all n elements without replacement, which is a permutation by definition.
OCaml's random permutation using Fisher-Yates: let shuffle list = let arr = Array.of_list list in let n = Array.length arr in for i = n - 1 downto 1 do let j = Random.int (i + 1) in let tmp = arr.(i) in arr.(i) <- arr.(j); arr.(j) <- tmp done; Array.to_list arr. Note the conversion to array and back — linked lists don't support O(1) random access needed by Fisher-Yates.
Full Source
#![allow(clippy::all)]
// Placeholder — pending conversionDeep Comparison
OCaml vs Rust: Random Permutation
Overview
See the example.rs and example.ml files for detailed implementations.
Key Differences
| Aspect | OCaml | Rust |
|---|---|---|
| Type system | Hindley-Milner | Ownership + traits |
| Memory | GC | Zero-cost abstractions |
| Mutability | Explicit ref | mut keyword |
| Error handling | Option/Result | Result<T, E> |
See README.md for detailed comparison.
Exercises
[1, 2, 3]. Count how often each of the 6 arrangements appears. They should each appear approximately 166,667 times.derangement(v: &[i32]) -> Vec<i32> that returns a permutation where no element appears in its original position. Use rejection sampling or the recursive algorithm.seeded_permutation(list: &[T], seed: u64) -> Vec<T> that produces a deterministic permutation — useful for reproducible testing and data augmentation.k_permutations<T: Clone>(list: &[T], k: usize) -> Vec<Vec<T>> that generates all ordered selections of k elements (not combinations). The count is P(n,k) = n!/(n-k)!.