给定一个偶数 (2k) 个元素的列表 L，我正在寻找一种算法来生成具有以下属性的 2k-1 个子列表的列表：
- 每个子列表恰好包含来自 L 的元素的 k 2-组合（顺序无关紧要的对），
- 每个子列表只包含 L 中的每个元素一次，并且
- 所有子列表中所有元素的并集恰好是 L 中所有可能的 2 组合的集合。
例如，如果输入列表是 L = [a, b, c, d]，我们有 k = 2 和 3 个子列表，每个子列表包括 2 对。一个可能的解决方案类似于 [[ab, cd], [ac, bd], [ad, bc]]。如果我们忽略列表中所有元素的排序（将所有列表视为集合），事实证明这也是 k = 2 的唯一解决方案。
我现在的目标不仅是找到一个单一的解决方案，而且是所有可能的解决方案。随着所涉及组合的数量快速增长，最好以巧妙的方式构建所有结果，而不是生成大量候选列表并从中删除不满足给定属性的元素。这样一个朴素的算法可能如下所示：
- 求 L 的所有 2-组合的集合 C。
- 求 C 的所有 k 组合的集合 D。
- 从 D 中选择所有并集等于 L 的集合，称为新集合 D'。
- 找到 D' 的所有 (2k-1) 组合的集合 E。
- 从 E 中选择所有集合，联合是集合 C，并让新集合作为最终输出。
这个算法很容易实现，但是对于更大的输入列表来说速度非常慢。那么有没有办法更有效地构建结果列表呢？
编辑：这是 L = [a,b,c,d,e,f] 的结果，k = 3，由上述算法计算得出：
[[[ab,cd,ef],[ac,be,df],[ad,bf,ce],[ae,bd,cf],[af,bc,de]],
[[ab,cd,ef],[ac,bf,de],[ad,be,cf],[ae,bc,df],[af,bd,ce]],
[[ab,ce,df],[ac,bd,ef],[ad,be,cf],[ae,bf,cd],[af,bc,de]],
[[ab,ce,df],[ac,bf,de],[ad,bc,ef],[ae,bd,cf],[af,be,cd]],
[[ab,cf,de],[ac,bd,ef],[ad,bf,ce],[ae,bc,df],[af,be,cd]],
[[ab,cf,de],[ac,be,df],[ad,bc,ef],[ae,bf,cd],[af,bd,ce]]]
满足所有性质：
- 每个子列表有 k = 3 2-组合，
- 每个子列表仅包含每个元素一次，并且
- 一个解决方案的所有 2k-1 = 5 个子列表的并集恰好是 L 的所有可能的 2 组合的集合。
编辑 2：根据 user58697 的回答，我使用循环锦标赛调度改进了计算算法：
- 令 S 为结果集，从一个空集开始，P 为 L 的所有排列的集合。
- 重复以下操作，直到 P 为空：
- 从 P 中选择任意排列
- 为此排列执行完整的 RRT 调度。在每一轮中，来自 L 的元素的排列形成 L 的一个排列。从 P 中移除所有这 2k 个排列。
- 将生成的计划添加到 S。
- 如果它们的子列表的并集具有重复元素（即不加起来为 L 的所有 2 组合），则从 S 中删除所有列表。
这个算法比第一个算法性能好得多。我能够将 k = 4 的结果数计算为 960，将 k = 5 的结果数计算为 67200。不过，这个序列似乎没有OEIS 结果的事实让我想知道这些数字是否真的正确，即如果算法正在生成完整的解决方案集。