sml-combinatorics

Combinatorial enumeration and exact counting in pure Standard ML — all permutations and the lexicographic nextPermutation successor, k-combinations, integer partitions, the reflected binary Gray code, and exact IntInf counts (binomial nCr, falling-factorial nPr, catalan, stirling2, and factorial). Built on the Basis library only: no FFI, no IO, no clock, no randomness, no threads, so it is fully deterministic and runs byte-identically under both MLton and Poly/ML.

This is an enumeration/counting library. Optimization problems such as the knapsack and interval scheduling live in the sibling sml-dp library and are intentionally out of scope here.

• 149 assertions, green on MLton and Poly/ML.
• Basis-library only — no external or vendored dependencies; the repo builds standalone.
• Pure & deterministic: all counting functions return IntInf.int, so they never overflow, and every result is identical across runs, machines, and compilers.

With smlpkg:

smlpkg add github.com/sjqtentacles/sml-combinatorics
smlpkg sync

Include the MLB from your own:

local
  $(SML_LIB)/basis/basis.mlb
  lib/github.com/sjqtentacles/sml-combinatorics/... (via smlpkg)
in
  ...
end

This brings structure Combinatorics into scope.

(* enumeration *)
val ps = Combinatorics.permutations [1,2,3]
(* [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] *)

val nxt = Combinatorics.nextPermutation Int.compare [1,2,3]   (* SOME [1,3,2] *)
val cs  = Combinatorics.combinations 2 [1,2,3,4]
(* [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] *)

val pt  = Combinatorics.partitions 4
(* [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] *)

val gc  = Combinatorics.grayCode 3       (* [0,1,3,2,6,7,5,4] *)

(* exact counting (IntInf) *)
val f   = Combinatorics.factorial 25     (* 15511210043330985984000000 *)
val c   = Combinatorics.nCr 52 5         (* 2598960 *)
val p   = Combinatorics.nPr 10 3         (* 720 *)
val cat = Combinatorics.catalan 10       (* 16796 *)
val s   = Combinatorics.stirling2 10 3   (* 9330 *)

(* enumeration *)
val permutations    : 'a list -> 'a list list
val nextPermutation : ('a * 'a -> order) -> 'a list -> 'a list option
val combinations    : int -> 'a list -> 'a list list
val partitions      : int -> int list list
val grayCode        : int -> int list

(* exact counting (over IntInf) *)
val factorial : int -> IntInf.int
val nCr       : int -> int -> IntInf.int
val nPr       : int -> int -> IntInf.int
val catalan   : int -> IntInf.int
val stirling2 : int -> int -> IntInf.int

The Combinatorics structure is sealed opaquely (:> COMBINATORICS), so only the signature is visible to consumers.

• permutations xs lists every permutation in lexicographic order of element positions — the input order is treated as the underlying total order — so for distinct input of length n it yields n! lists, head element varying slowest. permutations [] = [[]].
• nextPermutation cmp xs is the classic in-place-style successor (find pivot, swap with its least larger successor, reverse the suffix). It returns NONE when xs is already the last (non-increasing) arrangement; repeatedly applying it from the sorted list enumerates all n! permutations.
• combinations k xs lists every k-element sub-list, preserving the input order within and between subsets (lexicographic by index set). combinations 0 xs = [[]], and the result is [] when k < 0 or k > length xs.
• partitions n lists the integer partitions of n, each a weakly descending int list (largest part first) summing to n. partitions 0 = [[]] and partitions n = [] for n < 0. The count matches the partition numbers p(n) (OEIS A000041).
• grayCode n returns the n-bit reflected binary Gray code as the 2^n integer code words via the closed form g(i) = i xor (i div 2). Consecutive entries — and the wrap-around last/first pair — differ in exactly one bit, and the sequence is a permutation of 0 .. 2^n - 1. grayCode 0 = [0].
• Counting is exact over IntInf. factorial n and catalan n raise Domain for n < 0. nCr n k and nPr n k are 0 when k < 0 or k > n; nCr satisfies the symmetry nCr n k = nCr n (n-k) and Pascal's rule. stirling2 n k is the number of partitions of an n-set into k non-empty unlabelled blocks (stirling2 0 0 = 1), computed by the recurrence S(n,k) = k·S(n-1,k) + S(n-1,k-1).

make test        # MLton
make test-poly   # Poly/ML
make all-tests   # both
make example     # build + run examples/demo.sml
make clean

Both compilers run the same strict-TDD suite (149 assertions), seeded with closed-form vectors and cross-checks: permutation/combination counts equal nPr/nCr; the lexicographic ordering of permutations and combinations is pinned to hand-listed sequences; nextPermutation unfolds exactly to permutations; Gray-code lengths are 2^n, consecutive (and wrap-around) entries differ by one bit, and the sequence covers 0..2^n-1; partition counts match p(n) (A000041) and every part list is descending and sums to n; catalan/stirling2 match their closed forms and small table values (stirling2 row sums recover the Bell numbers A000110); and nCr symmetry, Pascal's rule, and 2^n row sums all hold.

make example prints a deterministic report — sample enumerations, the exact counting functions, and a Pascal's triangle (output is byte-identical under MLton and Poly/ML):

=== sml-combinatorics demo ====================================

Permutations of [1,2,3]  (lexicographic by input order)
  [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

nextPermutation walk from [1,2,3]
  [1,2,3]
  [1,3,2]
  [2,1,3]
  [2,3,1]
  [3,1,2]
  [3,2,1]

Combinations: choose 2 of [1,2,3,4]
  [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
Combinations: choose 3 of [1,2,3,4,5]
  [[1,2,3], [1,2,4], [1,2,5], [1,3,4], [1,3,5], [1,4,5], [2,3,4], [2,3,5], [2,4,5], [3,4,5]]

Integer partitions of 5  (largest part first)
  [[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1]]

Reflected binary Gray code, 3 bits
  [0,1,3,2,6,7,5,4]

Counting (exact over IntInf)
  10!            = 3628800
  25!            = 15511210043330985984000000
  C(52,5)        = 2598960
  P(10,3)        = 720
  catalan 10     = 16796
  S(10,3)        = 9330

Pascal's triangle (rows 0..7, from nCr)
  1
  1 1
  1 2 1
  1 3 3 1
  1 4 6 4 1
  1 5 10 10 5 1
  1 6 15 20 15 6 1
  1 7 21 35 35 21 7 1

===============================================================

CI builds Poly/ML 5.9.1 from source rather than using the Ubuntu package (Poly/ML 5.7.1), whose X86 code generator crashes (asGenReg raised while compiling) on some code. See .github/workflows/ci.yml.

MIT — see LICENSE.