Correctness of SUM enumeration via dynamic programming #
This file formalizes a subset-sum enumeration algorithm. The algorithm
enumerates the non-empty subsets W of a finite set of occurrences U
whose weighted sum ∑_{u ∈ W} t u satisfies (∑ t) op C for a fixed
comparison operator op and constant C : ℕ. The main result
sumDP_correct shows that the output coincides with that set in the
sense of membership.
The standard imperative presentation uses an in-place dp[j] array
bounded by some J chosen per operator, with early returns for
impossible operator/constant combinations. We use the mathematically
equivalent functional formulation: sumExact occs t j is the list of
subsets of occs.toFinset with weighted sum exactly j (i.e., dp[j]
after iteration N), defined by direct recursion on occs. The six
op-cases and all four early-return cases collapse into a single
flatMap over satisfying sums in {0, …, T}, where
T = occs.toFinset.sum t. Impossible sums simply contribute empty
enumerations.
The aggregate term t enters as α → ℕ; an annotation α_i would be
part of the occurrence type and does not enter the sum.
Definitions #
sumExact occs t j: enumerate the subsets of occs.toFinset whose
weighted sum under t is exactly j. Mirrors the dynamic-programming
table dp[j] after the outer loop: every subset either omits the head
u (left recursion) or includes it (right recursion, requires
t u ≤ j).
Equations
Instances For
Dependency graph
SumDP(U, t, C, op): top-level routine. The six operator-cases
(and the four early-return cases of a more imperative presentation)
collapse into a single flatMap over satisfying sums in {0, …, T},
where T is the total weight occs.toFinset.sum t.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Correctness lemmas #
Correctness of sumDP.
For a list occs of distinct occurrences, a weight function t, a
constant C : ℕ, and a comparison operator op, the list
sumDP occs t C op enumerates exactly the non-empty subsets
S ⊆ occs.toFinset whose weighted sum satisfies op.eval (S.sum t) C.
Dependency graph
Soundness of the implementation optimizations #
The imperative implementation of the algorithm bounds its dp table by an
operator-specific J = min(C, T) for the operators =, ≤, <, prunes
dp[j] cells beyond the running prefix sum, and short-circuits comparisons
that no achievable sum can satisfy. Each optimization is proved as a list
equality with the unoptimized enumeration: the optimized enumerations
return the same worlds, so the downstream ⊕-sum of world annotations is
unchanged.