如何求解满足特定约束的最小长度3元二项式系数子集问题

给定长度为n的数组keys[n]，构造符合约束的三元组数组combination[?][3]的问题属于组合设计领域的3-均匀超图构造问题，更具体来说是最小无孤边3-均匀超图问题：你要找的是边数最少的3元子集（超边）族，满足子集族覆盖所有n个键，且子集族包含的任意二元对（即每个三元组内3选2生成的子集）都至少出现在2个超边中——也就是不存在只在一个三元组里出现的“孤立二元对”。
它和经典覆盖设计的区别是，不需要覆盖全部C(n,2)个二元对，只需要保证你选中的三元组带出的二元对都满足出现次数≥2的要求。如果额外要求所有二元对出现次数恰好为2，这类结构也对应2-重三角分解的图构造，你给出的n=5的最优示例就属于这类结构。

下界计算 #

首先可以通过计数快速算出最小m（三元组数量）的理论下界，用来提前判断解的最优性：

• 每个三元组包含3个二元对，所有出现的二元对计数≥2，因此所有二元对的总出现次数3m ≥ 2E，其中E是选中三元组覆盖的不同二元对总数。
• 从总次数可以直接推导出：3m必须是偶数（因为2E是偶数），因此m如果算出来是奇数，至少要加1才能满足奇偶性要求。比如n=5时m=5的话总次数是15，为奇数，直接不可能成为可行解。
• 每个顶点至少出现在2个三元组中（如果某个顶点只在1个三元组里，那这个三元组里和它配对的两个二元对都只出现1次，违反约束），因此总度数和3m ≥ 2n，即m ≥ ⌈2n/3⌉，这个下界比较松，仅适合初步排查。
  当构造的解满足所有二元对恰好出现2次时，3m=2E，此时没有任何冗余计数，一定是最优解。

小规模n精确求解（n≤20） #

对于n比较小的场景，可以直接转化为带剪枝的回溯搜索，或者0-1整数规划问题求解，逻辑非常直接：

• 预先枚举所有C(n,3)个可能的三元组，给每个二元对维护一个计数器，记录当前已经选了多少个三元组包含它。
• 按顺序遍历三元组，每次决定选或不选，选了之后就给对应的3个二元对计数器加1。
• 剪枝规则：如果当前存在某个二元对计数器已经是1，但剩下还没遍历到的三元组里没有任何一个包含这个二元对，说明这个二元对永远没法把计数补到≥2，当前路径不可能出解，直接回退。
• 当遍历完所有三元组后，检查是否所有顶点都被覆盖、所有非0的二元对计数器都≥2，如果满足就记录当前的三元组数量，更新全局最优解。
  如果觉得手写回溯麻烦，也可以把规则写成0-1整数规划的约束，调用通用整数规划求解器计算，代码量会小很多。

大规模n构造（n>20） #

如果n很大不需要严格最优，可以用随机贪心+局部优化的方法快速得到接近最小长度的解，还能满足随机性和频次均匀的可选要求：

• 初始化空的三元组集合，随机从未选的三元组里采样加入，直到所有n个顶点都被覆盖。
• 遍历所有二元对，找出所有计数为1的二元对，每次优先选一个包含该二元对、且另外两个二元对当前计数最低的三元组加入，直到所有二元对计数要么是0要么≥2。
• 做局部精简：随机打乱现有三元组的顺序，依次尝试删除每个三元组，如果删除后仍然满足所有约束（没有出现计数为1的二元对、所有顶点仍被覆盖），就永久删除这个三元组，循环多轮直到没法再删除任何三元组。
• 如果需要满足频次均匀的要求，在选三元组的时候优先选能让各二元对计数方差最小的选项即可，每次生成时用不同的随机种子就能得到不同的最小长度解。

你给出的keys[5] = {1,2,3,4,5}对应的解就是严格最优解：

• 这个解一共6个三元组，总二元对出现次数是6*3=18，覆盖了9个不同的二元对，每个二元对恰好出现2次，刚好达到3m=2E的最优下界。
• 前面已经推导过m=5时总次数为15是奇数，不可能满足约束，因此不存在长度小于6的可行解。

内容的提问来源于stack exchange，提问作者Yakuwari