Combinatorics — factorial, permutations, combinations factorial folds product over range(1, n+1)
nPr = n!/(n-r)! and nCr = n!/(r!(n-r)!). To stay exact for larger n we compute nCr with a running product instead of three separate factorials. Pascal's identity is the cross-check: C(n,r) = C(n-1,r-1) + C(n-1,r).
A Soma program from the math part of the verified corpus: 64 lines, cells Combinatorics, ComboTests. It passes soma check with soma 3.2.4.
How it is built
The cell Combinatorics declares 4 signals in its face: factorial(n: Int) -> Int, perm(n: Int, r: Int) -> Int, choose(n: Int, r: Int) -> Int and run() -> Map. Handlers: factorial (line 21), perm (line 26), choose (line 30) and run (line 39).
The file also holds 1 test cell (ComboTests) with 7 assertions, run by soma test.
The source
combinatorics.cell
// ============================================================================
// Combinatorics — factorial, permutations, combinations
// ============================================================================
//
// factorial folds product over range(1, n+1). nPr = n!/(n-r)! and nCr =
// n!/(r!(n-r)!). To stay exact for larger n we compute nCr with a running
// product instead of three separate factorials. Pascal's identity is the
// cross-check: C(n,r) = C(n-1,r-1) + C(n-1,r).
//
// soma run combinatorics.cell run
// ============================================================================
cell Combinatorics {
face {
signal factorial(n: Int) -> Int
signal perm(n: Int, r: Int) -> Int
signal choose(n: Int, r: Int) -> Int
signal run() -> Map
}
on factorial(n: Int) {
if n <= 1 { return 1 }
return product(range(1, n + 1))
}
on perm(n: Int, r: Int) {
return idiv(factorial(n), factorial(n - r))
}
on choose(n: Int, r: Int) {
// multiplicative formula: product over i of (n-r+i)/i
let result = 1
for i in range(1, r + 1) {
result = idiv(result * (n - r + i), i)
}
return result
}
on run() {
return map(
"fact_6", factorial(6),
"perm_5_2", perm(5, 2),
"choose_5_2", choose(5, 2),
"choose_10_3", choose(10, 3)
)
}
}
cell test ComboTests {
rules {
assert factorial(0) == 1
assert factorial(6) == 720
// 5 permute 2 = 20
assert perm(5, 2) == 20
// 5 choose 2 = 10
assert choose(5, 2) == 10
assert choose(10, 3) == 120
// symmetry: C(n,r) = C(n,n-r)
assert choose(10, 3) == choose(10, 7)
// Pascal's identity
assert choose(10, 3) == choose(9, 2) + choose(9, 3)
}
}What the toolchain says
$ soma check combinatorics.cell
✓ All checks passed.$ soma test combinatorics.cell
test ComboTests ...
✓ assert factorial(0) == 1
✓ assert factorial(6) == 720
✓ assert perm(5, 2) == 20
✓ assert choose(5, 2) == 10
✓ assert choose(10, 3) == 120
✓ assert choose(10, 3) == choose(10, 7)
✓ assert choose(10, 3) == choose(9, 2) + choose(9, 3)
7 tests: 7 passed, 0 failed$ soma verify combinatorics.cell
Verifying combinatorics.cell...
No state machine in this program: nothing to prove beyond `soma check` (invariants and lifecycles are what verify proves).
VERIFY OK (vacuous — no state machine)$ soma run combinatorics.cell run
{"fact_6": 720, "perm_5_2": 20, "choose_5_2": 10, "choose_10_3": 120}