latin-sampler

MCMC sampler for generating approximately uniform Latin squares — n×n arrays where each row and column is a permutation of {0, 1, ..., n-1}.

Features

Approximately uniform — Jacobson-Matthews algorithm with verified uniformity (χ²/df ≈ 1.0)
Reproducible — Deterministic output with seed specification
Efficient — Iterator mode is ~3x faster than one-shot for bulk sampling (amortized burn-in)
WebAssembly support — Try the interactive demo

Installation

[dependencies]
latin-sampler = "0.1"

Optional features:

serde — Enable serialization for LatinSquare

Algorithm

Uses the Jacobson-Matthews algorithm (1996), proven to be ergodic — any Latin square can be reached from any starting state, guaranteeing the sampler explores the full space.

Reference: Jacobson & Matthews, "Generating uniformly distributed random Latin squares", J. Combinatorial Designs 4(6), 1996.

Example

use latin_sampler::{Sampler, SamplerParams};
use rand_chacha::ChaCha20Rng;
use rand::SeedableRng;

let rng = ChaCha20Rng::seed_from_u64(42);
let mut sampler = Sampler::new(8, rng, SamplerParams::default());

let sq = sampler.next().unwrap();
for r in 0..sq.n() {
    for c in 0..sq.n() {
        print!("{} ", sq.get(r, c));
    }
    println!();
}
// Output (seed=42):
// 0 2 4 3 6 7 5 1
// 1 5 2 7 0 4 6 3
// 6 7 3 4 1 5 0 2
// 2 6 0 5 4 3 1 7
// 3 4 6 0 7 1 2 5
// 7 1 5 2 3 0 4 6
// 5 0 7 1 2 6 3 4
// 4 3 1 6 5 2 7 0

Or from command line: cargo run --release --example generate -- 8 42

Default Parameters

Parameter	Default	Description
burn_in	n^3	Steps to reach equilibrium
thinning	3*n^2	Steps between samples for independence
p_do_nothing	0.01	Probability of null move (aperiodicity)

Uniformity Verification

Question: Does the sampler produce all Latin squares with equal probability?

Chi-square goodness-of-fit test confirms uniform distribution. χ²/df ≈ 1.0 means uniform; values < 1.2 are acceptable.

n	Iterator	One-shot
4	1.03	0.94
5	1.03	1.01
6	1.00	1.00
7	1.01	0.99
8	1.02	0.99

Sampling modes:

Iterator (Sampler): Burn-in once, then thinning steps between samples. Efficient for many samples.
One-shot (sample()): Fresh burn-in with each seed. Fully independent samples.

Performance: When generating multiple samples, Sampler is ~3x faster than repeated sample() calls (n=10, k≥100). This is because sample() performs n³ burn-in steps each call, while Sampler only does 3n² thinning steps after the initial burn-in.

Verify with: cargo run --release --example uniformity_test -- <n> [--light] [--oneshot] Benchmark with: cargo run --release --example benchmark_comparison -- [n]

Independence Verification (Iterator mode)

Question: Are consecutive samples from Sampler independent of each other?

With default thinning (3n²), consecutive samples show negligible correlation:

n	thinning	tau	\|rho1\|
5	75	~1.03	~0.01
7	147	~1.04	~0.01
9	243	~1.03	~0.01
11	363	~1.04	~0.01
15	675	~1.04	~0.01
20	1200	~1.04	~0.01
26	2028	~1.05	~0.01

tau (integrated autocorrelation time): tau ≈ 1.0 means each sample counts as ~1 independent sample.
|rho1| (lag-1 autocorrelation): |rho1| < 0.05 means consecutive samples are nearly uncorrelated.

Verify with: cargo run --release --example independence_check

Notes

Output is deterministic given the same seed and parameters
Default burn_in (n³) and thinning (3n²) are empirically validated for n ≤ 26
For custom thinning: SamplerParams { thinning: Some(100), ..Default::default() }
Requires Rust 1.85+ (edition 2024)

latin-sampler 0.1.1