One bounded step of ranked subset enumeration
ProvedLax263307Proofs.NativeCombinations.subset_entry_spec_nativealgorithmscomputational-complexitygraph-theory
Suppose , the remaining selection count is at most , the current rank is below , and all required binomial coefficients and table addresses are below . Given the full binomial table prefix, the fixed subset-entry command returns the next inclusion bit and updates the remaining count and rank exactly according to the enumeration transition:
The operational cost is at most forty steps.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeNextInterfaces namespace Lax263307Proofs.NativeCombinations end Lax263307Proofs.NativeCombinations
Formal statement
theorem Lax263307Proofs.NativeCombinations.subset_entry_spec_native : ∀ (B n k i need rank : Nat),
@LT.lt Nat instLTNat i n →
@LE.le Nat instLENat need k →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) n
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) k
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
n)
k)
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
B →
@LT.lt Nat instLTNat rank B →
(∀ (i : Nat),
@LE.le Nat instLENat i n → ∀ (j : Nat), @LE.le Nat instLENat j k → @LT.lt Nat instLTNat (i.choose j) B) →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (σ.vars "choose.n") n)
(And
(@Eq Nat (σ.vars "choose.cols")
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) k
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And (@Eq Nat (σ.vars "subset.i") i)
(And (@Eq Nat (σ.vars "subset.need") need)
(And (@Eq Nat (σ.vars "subset.rank") rank)
(Lax455465Proofs.RamVirtualState.Prefix (Lax263307Proofs.NativeCombinations.table n k)
"choose.table" σ))))))
Lax263307Proofs.NativeCombinations.subsetEntry
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And
(@Eq Nat (τ.vars "subset.bit")
(@Prod.fst Nat (Prod Nat Nat)
(Lax263307Proofs.NativeCombinations.advance
(@HSub.hSub Nat Nat Nat (@instHSub Nat instSubNat) n i) need rank)))
(And
(@Eq Nat (τ.vars "subset.need")
(@Prod.fst Nat Nat
(@Prod.snd Nat (Prod Nat Nat)
(Lax263307Proofs.NativeCombinations.advance
(@HSub.hSub Nat Nat Nat (@instHSub Nat instSubNat) n i) need rank))))
(@Eq Nat (τ.vars "subset.rank")
(@Prod.snd Nat Nat
(@Prod.snd Nat (Prod Nat Nat)
(Lax263307Proofs.NativeCombinations.advance
(@HSub.hSub Nat Nat Nat (@instHSub Nat instSubNat) n i) need rank))))))
(@OfNat.ofNat Nat (nat_lit 40) (instOfNatNat (nat_lit 40))) := by sorrySource