20个元素不重叠配对组合的计算疑问及算法结果咨询

嗨，我来帮你理清楚这个问题～首先先给你一个核心结论：从理论上来说，20个元素最多可以分出19组完全不重复的「10个不重叠配对」（也就是覆盖所有20个元素的完美匹配），但你的算法只得到9组，大概率是因为算法的配对选择策略不是最优的，导致提前进入了无法继续组成完整配对组的状态。

先说说理论上的上限为什么是19组 #

我们可以把20个元素看成20个点，每一个配对就是两点之间的一条连线，这样就构成了一个「完全图」（每个点和其他19个点都有连线），总共有 C(20,2)=190 条连线——这和你算的190个配对完全一致。

你要找的「10个不重叠配对」，在图论里叫做完美匹配：它刚好覆盖所有20个点，没有重复使用任何点，每条连线只对应一个配对。而把整个完全图的所有连线，分成若干个没有重复连线的完美匹配，这个操作叫做「1-因子分解」。

对于偶数个顶点的完全图 K_n，它是可以完成1-因子分解的，分解出来的完美匹配数量刚好是 n-1（也就是20-1=19组）。原因很直观：每个元素和其他19个元素都能配对，每个完美匹配里每个元素只用掉一个配对，所以刚好可以分19组，每组用掉每个元素的一个新配对，直到所有190个配对都被用完。

为什么你的算法只得到9组？ #

你的算法逻辑是：先列出所有可能的配对，然后每次选一个配对，标记这两个元素为已用，继续选不包含已用元素的配对，凑够10个组成一组；之后把用过的配对从列表里删掉，重复这个过程。

问题就出在这种贪心式的随机/顺序选择策略上：它不一定能保证每次选的配对组合，能让剩余的配对依然可以组成完整的完美匹配。比如，可能选到第9组之后，剩余的配对分布变得零散——有的元素只剩1个配对可用，有的元素剩多个，甚至出现了奇数个度数为奇数的顶点（根据图论的握手定理，这样的图是不可能存在完美匹配的），导致你无法再凑出10个完全不重叠的配对。

举个简化的小例子：比如4个元素A、B、C、D，理论上可以分3组完美匹配：(AB, CD)、(AC, BD)、(AD, BC)。但如果贪心选择时留下了无法配对的零散边，就会提前结束。在20个元素的场景下，这种情况更容易发生。

想要得到理论上限的19组，该怎么做？ #

如果想拿到完整的19组不重复配对，你需要用更系统的1-因子分解构造方法，而不是贪心选择。比如经典的旋转法：

• 把20个元素中的19个排成一个正19边形，第20个元素放在图形中心；
• 第一次：让中心元素和正19边形的顶点1配对，然后把顶点2和顶点19配对、顶点3和顶点18配对……以此类推，得到第一组完美匹配；
• 第二次：把正19边形的配对整体旋转一个位置——中心元素和顶点2配对，顶点3和顶点1配对、顶点4和顶点19配对……以此类推；
• 重复这个旋转操作，直到完成19次，就能得到19组完全不重复的完美匹配，刚好用完所有190个配对。

备注：内容来源于stack exchange，提问作者Danilo Lemes