Fixed-width word records and bounded-subset decoding
DefinitionStableMSR_BoundedWordCatalogWords of length over digits are listed lexicographically. Digit zero is padding and digit represents vertex ; decoding deletes zeros and repeated digits. Each word is stored as a width header followed by its digits in consecutive integer-memory cells. The catalog begins at address , and its reader uses fixed record width . These definitions specify exact catalog contents and memory readback; different words may represent the same subset.
Definition code
import Definitions.Def_StableMSR_StructuredCompiler open scoped Classical namespace StableMSR.Recovery.BoundedSubsetWords def words (n : ℕ) : ℕ → List (List ℕ) | 0 => [[]] | w+1 => (List.range (n+1)).flatMap (fun a => (words n w).map (List.cons a)) def decode (n : ℕ) (l : List ℕ) : Finset (Fin n) := Finset.univ.filter (fun v => v.val+1 ∈ l) end StableMSR.Recovery.BoundedSubsetWords namespace StableMSR.Recovery.Compiler.TupleWriter def writeMemory (base : ℤ) (values : List ℤ) (mem : ℤ → ℤ) : ℤ → ℤ := match values with | [] => mem | v::vs => writeMemory (base+1) vs (Function.update mem base v) end StableMSR.Recovery.Compiler.TupleWriter namespace StableMSR.Recovery.Compiler.TupleEnumeration open TupleWriter BoundedSubsetWords def wordStream (n w : ℕ) (pre : List ℤ) (r : ℕ) : List ℤ := (words n r).flatMap (fun xs : List ℕ => (w : ℤ) :: (pre ++ xs.map (fun i : ℕ => (i : ℤ)))) def readWord (w : ℕ) (mem : ℤ → ℤ) (base : ℤ) : List ℕ := (List.range w).map (fun i : ℕ => (mem (base+1+(i : ℤ))).toNat) def catalogWords (n w : ℕ) (mem : ℤ → ℤ) : List (List ℕ) := (List.range ((n+1)^w)).map (fun j : ℕ => readWord w mem (2+((w+1)*j : ℕ))) end StableMSR.Recovery.Compiler.TupleEnumeration
Source
Concrete bounded-width enumeration kernel for the Exact Sum-of-Radii Clustering under Any Constant Stability mission, over Definitions.Def_StableMSR_Recovery_Execution and the verified structured compiler.