给定一个由偶数(2k)个元素组成的列表L，我正在寻找一种算法来生成具有以下属性的2k-1个子列表：
1. 每个子列表都包括恰好k个来自L的2-组合(顺序不重要的对)。 2. 每个子列表都恰好包含来自L的每个元素一次。 3. 所有子列表中的所有元素的并集正好是L的所有可能的2-组合集合。
例如，如果输入列表为L=[a,b,c,d]，则我们有k=2和3个子列表，每个子列表包括2个对。一个可能的解决方案看起来像[[ab,cd],[ac,bd],[ad,bc]]。如果忽略列表中所有元素的顺序(将所有列表视为集合)，那么它也是k=2的唯一解决方案。
现在我的目标不仅是找到单个解决方案，而且要找到所有可能的解决方案。由于涉及的组合数量增长得非常快，因此最好以聪明的方式构建所有结果，而不是生成一个巨大的候选列表，并从中删除不符合给定属性的元素。这样一个天真的算法可能如下所示：
1. 找出L的所有2-组合的集合C。 2. 找出C的所有k-组合的集合D。 3. 选择所有联合等于L的集合从D中，称新集合为D'。 4. 找出D'的所有(2k-1)-组合的集合E。 5. 选择所有联合是集合C的集合从E中，并将新集合作为最终输出。
这个算法很容易实现，但对于更大的输入列表来说非常慢。那么有没有一种更有效地构建结果列表的方法呢？
编辑：下面是L=[a,b,c,d,e,f]，k=3时上述算法计算的结果：
1. 每个子列表都包括恰好k个来自L的2-组合(顺序不重要的对)。 2. 每个子列表都恰好包含来自L的每个元素一次。 3. 所有子列表中的所有元素的并集正好是L的所有可能的2-组合集合。
例如，如果输入列表为L=[a,b,c,d]，则我们有k=2和3个子列表，每个子列表包括2个对。一个可能的解决方案看起来像[[ab,cd],[ac,bd],[ad,bc]]。如果忽略列表中所有元素的顺序(将所有列表视为集合)，那么它也是k=2的唯一解决方案。
现在我的目标不仅是找到单个解决方案，而且要找到所有可能的解决方案。由于涉及的组合数量增长得非常快，因此最好以聪明的方式构建所有结果，而不是生成一个巨大的候选列表，并从中删除不符合给定属性的元素。这样一个天真的算法可能如下所示：
1. 找出L的所有2-组合的集合C。 2. 找出C的所有k-组合的集合D。 3. 选择所有联合等于L的集合从D中，称新集合为D'。 4. 找出D'的所有(2k-1)-组合的集合E。 5. 选择所有联合是集合C的集合从E中，并将新集合作为最终输出。
这个算法很容易实现，但对于更大的输入列表来说非常慢。那么有没有一种更有效地构建结果列表的方法呢？
编辑：下面是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组合，
- 每个子列表只包含每个元素一次，
- 一个解的五个子列表的并集正好是L的所有可能的2组合。
编辑2：基于用户58697的答案，我通过使用轮换赛程安排来改进了计算算法：
- 让S成为结果集，从一个空集开始，P是L的所有排列的集合。
- 重复以下步骤，直到P为空：
- 从P中选择任意排列
- 对于此排列执行完整的RRT调度。在每一轮中，来自L的元素的排列形成L的排列。从P中删除所有这些2k个排列。
- 将得到的日程表添加到S中。
- 如果它们的子列表的并集具有重复元素（即不等于L的所有2组合），则从S中删除所有列表。
这个算法比第一个算法更有效率。我能够计算出k = 4时的结果数为960，k = 5时的结果数为67200。这个序列似乎没有OEIS结果，这让我怀疑这些数字是否正确，即算法是否生成了完整的解集。