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结果,这让我怀疑这些数字是否正确,即算法是否生成了完整的解集。