python algorithms-submodular-rounding-check.py
python -O algorithms-submodular-rounding-check.py两个命令只向stdout输出同一份JSON。整数和有理数用Fraction；这些例子不是大规模优化器的性能测试。提交内容需要同时说明可行性、坐标边缘、目标期望以及计算代价，不能只展示一个成功分支。
一、给同一个分数点三种不同解释
底集按a=0、b=1、c=2、d=3编号。覆盖集合为
a: 0,1,2
b: 0,3,4
c: 0,1,2
d: 5f(S)为被覆盖区域数。拟阵约束为a、b最多选一项，c、d最多选一项；全部基是ac、ad、bc、bd。
先不执行，写出独立随机子集期望：区域0未覆盖概率为(1−xₐ)(1−x_b)(1−x_c)，区域1、2为(1−xₐ)(1−x_c)，区域3、4只取决于b，区域5只取决于d。令各xᵢ=1/2，应得F=31/8、梯度(5/4,9/4,5/4,1)。
随后分别算三份同边缘分布：
- 独立选各元素：F=31/8，但两组配额同时可行概率只有9/16
- 以各1/2直接选输入基ac或bd：每次可行，平均7/2
- 以各1/4选四种基：每次可行，平均4
这三份数值构成一个真正边界：只验证边缘为1/2，既不能证明可行性，也不能决定子模目标期望。说明第三份分布如何由第三题的算法产生，而不是事后任意指定四个概率。
二、把十二个方向保存成可复用的基分解
普通逐项贪心先选a，后选d，覆盖值4；最优bc覆盖5。现在执行有限步连续贪心，L=12，δ=1/12。
第0轮梯度(3,3,3,1)，按固定编号消除平局，方向为ac。第一步后x=(1/12,0,1/12,0)。下一轮梯度为(11/4,409/144,11/4,1)，方向转为bc。核b的梯度比a大，而不是仅看小数近似。
JSON中euler.history保存全部12轮：每行含本轮梯度、所选基、更新前后坐标。后11轮都是bc，最终
x = (1/12, 11/12, 1, 0)
x = (1/12) 1_ac + (11/12) 1_bc
F(x) = 29/6逐坐标核上式分解。方向是整个可行基的指标；每轮只加入1/12份，不能把第一轮“选过a”解释为此后a已经永久占满第一组配额。
本例r=2、精确梯度η=0，通用有限步保证为
1 - (11/12)^12 - 1/12 ≈ 0.565实际相对值为(29/6)/5=29/30。分别提交通用界和实际值，不把12步过程称为已精确达到连续极限的1−1/e证明。
三、枚举两次交换，验证完整分布
先用另一份输入分解(1/2)ac+(1/2)bd。按交换舍入，第一次i=a，唯一满足两侧都为基的j=b。公平分支分别得到“ac与ad”或“bc与bd”，再交换c、d。
| 输出 | 概率 | f值 |
|---|---|---|
| ac | 1/4 | 3 |
| ad | 1/4 | 4 |
| bc | 1/4 | 5 |
| bd | 1/4 | 4 |
检查概率和为1，所有基满足配额，每个坐标边缘1/2，平均4≥31/8。ac分支值3低于31/8，解释为什么这不违反期望保证。
JSON的half_basis_rounding同时列出F、舍入均值、直接抽原基均值和独立可行概率。再对所有16个元素子集A，检查P(A⊆B)≤∏ᵢ∈Axᵢ和P(A∩B=∅)≤∏ᵢ∈A(1−xᵢ)，共32项。这里没有声称坐标独立。
接着舍入第二题实际得到的分解，输出ac概率1/12、bc概率11/12，期望29/6。把两个合并分支都错误地取1/2，会把边缘变成1/2；用秩1输入(1/3){a}+(2/3){b}也能立即检出这个错误。
四、同一舍入器处理图拟阵
给四顶点图，五条边按ID列为
0: 0--1
1: 1--2
2: 2--3
3: 3--0
4: 0--2独立性oracle判森林。输入树012权重1/3、树034权重2/3，不添加任何配额分组信息。
输出分布为012:1/9、013:2/9、024:2/9、034:4/9。逐分支用连通与无环核它确为生成树，边缘应为(1,1/3,1/3,2/3,2/3)。若把每条边视为覆盖两个端点，所有输出树均覆盖4点，期望4；独立随机边集的同一目标期望只有98/27。
这项迁移要求真实调用森林oracle，不能把分区拟阵里的“交换同组元素”硬编码到新图上。各次候选交换要同时检查两棵树，单独保证一侧合法仍不够。
五、统计预算、loop与实现成本
给每轮每坐标加性容差ηM₁，总失败预算ρ。写出共同充分样本数
K ≥ ceil( ln(2 n L / ρ) / (2 η²) )附件gradient_budget另用整数H=ceil(log₂(2nL/ρ))上界自然对数，以ceil(H/(2η²))给保守但不依赖浮点舍入的样本数。n=4、L=12、η=1/20、ρ=1/10时返回K=2000，预算192000次value调用和288000次Bernoulli抽取；这是充分预算表，不伪装成已执行的64样本演示。
说明当前x依赖过去样本时，为何应先条件于全部过去，再对新样本用Hoeffding。各误差事件不必独立；新抽样必须符合当前x，不能把同一批随机子集不加分析地永久复用。
若分数点在好事件上至少为A·OPT，交换舍入之后无条件期望至少为(1−ρ)A·OPT。把它改写成“每个输出都满足A·OPT”是不成立的。附件64样本的分支只展示执行与费用，并未声称任意η、ρ共同界；sampled_demo.cost列出实际2nLK次value调用及n(n−1)LK次Bernoulli抽取。
加入一个不可独立的loopℓ，单例价值10⁶。可行最优仍为5，算法应先删除ℓ，再得M₁=3。JSON的loop.point保留原编号的零坐标。解释不删loop时M₁≤OPT为什么不成立，以及为什么仅给f(∅)=0不足以保证任意oracle单调子模。
最后区分单次采样算法与全分支诊断。一次舍入至多r(m−1)交换；枚举全部随机分支可能指数增长。精确梯度也枚举全部子集，指数成本已写入正文。每轮保留原底集长向量和完整轨迹还有复制及存储费用；有理数算术次数不等于任意位长整数运算均为常数。
提交三种分布、12轮记录、两个舍入输入的完整概率表、图拟阵迁移、loop反例和采样预算。空底集、全loop及零目标由附件另行返回可行边界结果，不使用空max或零除法。