查找给定列表的所有 2 种组合的某些排列

Finding certain arrangements of all 2-combinatons for a given list

给定一个包含偶数 (2k) 个元素的列表 L，我正在寻找一种算法来生成具有以下属性的 2k-1 个子列表的列表：

  1. 每个子列表恰好包含来自 L,
    2. 的元素的 k 个 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. 从D中选择并集等于L的所有集合，称为新集合D'。
  4. 找到 D' 的所有 (2k-1) 组合的集合 E。
  5. 从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]]]

所有属性都满足：

  1. 每个子列表有 k = 3 个 2-组合，
  2. 每个子列表只包含每个元素一次，并且
  3. 一个解决方案的所有 2k-1 = 5 个子列表的并集恰好是 L 所有可能的 2-组合的集合。

编辑2：根据user58697的回答，我改进了计算算法，使用循环赛调度：

  1. 设S为结果集，从一个空集开始，P为L的所有排列的集合。
  2. 重复以下直到P为空：
    • Select P
      • 的任意排列
    • 为此排列执行完整的 RRT 调度。在每一轮中，L中的元素排列形成L的排列。将P中的这2k个排列全部移除。
    • 将生成的时间表添加到 S。
  3. 如果子列表的联合具有重复元素（即不加起来不等于 L 的所有 2 个组合），则从 S 中删除所有列表。

该算法比第一个算法性能更高。我能够计算出 k = 4 的结果数为 960，k = 5 的结果数为 67200。这个序列似乎没有 OEIS result 的事实让我想知道这些数字是否真的正确，但是，即如果算法正在生成完整的解决方案集。

这是一个round-robin锦标赛安排：

  1. 一对是一对，
  2. 一个名单就是一轮（每支球队与另一支球队比赛）
  3. 一组名单就是一场完整的锦标赛（每支球队只与另一支球队交手一次）。

看看here.

这是一个有趣的问题。在回答的过程中（基本上是写完下面的程序，然后在OEIS上查序列），我了解到这个问题有一个名字和丰富的理论：what you want is to generate all 1-完整图 K2k.

的分解

让我们首先用那种语言重述问题：

给你一个数字 k 和一个大小为 2k 的列表（集合）L。我们可以把L看作一个完备图K2k.

的顶点集
  • 例如，k=3，L可以是{a, b, c, d, e, f}

A 1-factor（又名完美匹配）是将 L 划分为无序对（大小为 2 的集合）。即是k对的集合，其不相交并集为L。

  • 例如，ab-cd-ef是L的1因子= {a, b, c, d, e, f}。也就是说a匹配b，c匹配d，并且 e 与 f 匹配。这样，L就被分成了三组{a，b}，{c，d}, 和 {e, f}, 并集为 L.

设S（题中称为C）表示L的所有元素对的集合。（对于完全图来说，如果L是它的顶点集，S是它的边集。）注意S包含 (2k 选择 2) = k(2k-1) 对。因此对于 k = 0, 1, 2, 3, 4, 5, 6...，S 的大小为 0, 1, 6, 15, 28, 45, 66….

  • 例如，S = {ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef} 对于我们上面的 L (k = 3,所以 |S| = k(2k-1) = 15).

A 1-分解 是将 S 划分为集合，每个集合本身都是 1 因子（完美匹配）。请注意，由于这些匹配中的每一个都有 k 对，并且 S 的大小为 k(2k-1)，因此分区的大小为 2k-1（即，由 2k-1 个匹配组成）。

  • 例如，这是一个 1 因式分解：{ab-cd-ef, ac-be-df, ad- bf-ce,ae-bd-cf, af-bc-de}

换句话说，S 的每个元素（每对）恰好出现在 1-因式分解的一个元素中，L 的每个元素在 1-因式分解的每个元素中恰好出现一次。

问题要求生成所有 1-因式分解。

设M表示L的所有1-因子（所有完美匹配）的集合。很容易证明M包含(2k)!/(k!2^k) = 1×3×5× …×(2k-1) 匹配。对于k = 0, 1, 2, 3, 4, 5, 6…，M的大小为1, 1, 3, 15, 105, 945, 10395….

  • 比如我们上面的L，M = {ab-cd-ef, ab-ce-df, ab- cf-de,ac-bd-ef, ac-be-df, ac-bf-de,ad-bc -ef,ad-be-cf, ad-bf-ce, ae-bc-df, ae-bd- cf, ae-bf-cd, af-bc-de,af-bd-ce, af-be-cd }（对于 k=3，这个数字 15 与对的数量相同，但这只是一个巧合，你可以从其他数字中看出：这个数字的增长速度比 pai 的数量快得多rs.)

M容易生成：

def perfect_matchings(l):
    if len(l) == 0:
        yield []
    for i in range(1, len(l)):
        first_pair = l[0] + l[i]
        for matching in perfect_matchings(l[1:i] + l[i+1:]):
            yield [first_pair] + matching

例如，调用 perfect_matchings('abcdef') 会按预期生成 15 个元素 ['ab', 'cd', 'ef'], ['ab', 'ce', 'df'], ['ab', 'cf', 'de'], ['ac', 'bd', 'ef'], ['ac', 'be', 'df'], ['ac', 'bf', 'de'], ['ad', 'bc', 'ef'], ['ad', 'be', 'cf'], ['ad', 'bf', 'ce'], ['ae', 'bc', 'df'], ['ae', 'bd', 'cf'], ['ae', 'bf', 'cd'], ['af', 'bc', 'de'], ['af', 'bd', 'ce'], ['af', 'be', 'cd']。

根据定义，1 次分解是将 S 划分为 M 中的元素。或者等效地，M 的任何 (2k-1) 个不相交元素形成 1 次分解。这适用于直接的回溯算法：

  • 从一个空列表开始（部分分解）
  • 对于完美匹配列表中的每个匹配，尝试将其添加到当前的部分分解中，即检查它是否不相交（它不应包含任何已使用的对）
    • 如果没问题，将其添加到偏分解中，并尝试扩展

在代码中：

matching_list = []
pair_used = defaultdict(lambda: False)
known_matchings = []  # Populate this list using perfect_matchings()
def extend_matching_list(r, need):
    """Finds ways of extending the matching list by `need`, using matchings r onwards."""
    if need == 0:
        use_result(matching_list)
        return
    for i in range(r, len(known_matchings)):
        matching = known_matchings[i]
        conflict = any(pair_used[pair] for pair in matching)
        if conflict:
            continue  # Can't use this matching. Some of its pairs have already appeared.
        # Else, use this matching in the current matching list.
        for pair in matching:
            pair_used[pair] = True
        matching_list.append(matching)
        extend_matching_list(i + 1, need - 1)
        matching_list.pop()
        for pair in matching:
            pair_used[pair] = False

如果您使用 extend_matching_list(0, len(l) - 1) 调用它（在填充 known_matchings 之后），它会生成所有 1-因式分解。我已经把执行此操作的完整程序放在 here. With k=4 (specifically, the list 'abcdefgh'), it outputs 6240 1-factorizations; the full output is here.

正是在这个时候，我将序列1、6、6240输入到OEIS中，发现了OEIS A000438, sequence 1, 1, 6, 6240, 1225566720, 252282619805368320,…。表明对于k=6，解数≈2.5×1017意味着我们可以放弃生成所有解的希望。即使对于 k=5，≈10 亿个解决方案（回想一下我们试图从 |M|=945 个匹配项中找到 2k-1=9 个不相交的集合）也需要一些精心优化的程序。

第一个优化（令人尴尬的是，我后来通过仔细查看 k=4 的跟踪输出才意识到）是（在自然词典编号下）first[=297= 的索引] 在分区中选择的匹配不能大于 k-1 的匹配数。这是因为 S 的字典顺序第一个元素（如“ab”）只出现在那些匹配中，如果我们晚于这个开始，我们将永远不会在任何其他匹配中再次找到它.

第二个优化来自回溯程序的瓶颈通常是测试当前候选人是否可以接受。我们需要有效地测试不相交性：给定的匹配（在我们的部分分解中）是否与所有先前匹配的并集不相交。 （它的 k 对中的任何对是否是先前匹配已经覆盖的对之一。）对于 k=5，事实证明 S 的大小（2k 选择 2）= 45 小于 64，因此我们可以用 64 位整数类型紧凑地表示一个匹配（毕竟是 S 的一个子集）：如果我们将这些对编号为 0 到 44，那么任何匹配都可以用一个在对应于元素的位置具有 1 的整数表示它包含。然后测试不相交性是对整数的简单按位运算：我们只是检查当前候选匹配​​的 bitwise-AND 和偏分解中先前匹配的累积并集 (bitwise-OR) 是否为零。

执行此操作的 C++ 程序是 here, and just the backtracking part (specialized for k=5) does not need any C++ features so it's extracted out as a C program here。它在我的笔记本电脑上运行大约 4-5 小时，并找到所有 1225566720 个 1-因式分解。

看待这个问题的另一种方式是说如果 M 的两个元素相交（有一对（S 的元素）公共），则它们之间有一条边，并且我们正在寻找所有最大值M 中的独立集。同样，解决该问题的最简单方法可能仍然是回溯（我们将编写相同的程序）。

通过利用问题中的对称性，我们的程序可以变得更加高效：例如，我们可以选择任何匹配作为 1-因子分解中的第一个 1-因子（然后通过重新标记生成其余的，注意不要避免重复）。这就是 K12（当前记录）的 1 分解数的计算方式。

生成所有解的智慧笔记

在 The Art of Computer Programming 第 4A 卷中，在第 7.2.1.2 节 Generating All Permutations 的结尾，Knuth 有这个重要的一条建议：

Think twice before you permute. We have seen several attractive algorithms for permutation generation in this section, but many algorithms are known by which permutations that are optimum for particular purposes can be found without running through all possibilities. For example, […] the best way to arrange records on a sequential storage […] takes only O(n log n) steps. […] the assignment problem, which asks how to permute the columns of a square matrix so that the sum of the diagonal elements is maximized […] can be solved in at most O(n3) operations, so it would be foolish to use a method of order n! unless n is extremely small. Even in cases like the traveling salesrep problem, when no efficient algorithm is known, we can usually find a much better approach than to examine every possible solution. Permutation generation is best used when there is good reason to look at each permutation individually.

这似乎是这里发生的事情（来自问题下方的评论）：

I wanted to calculate all solutions to run different attribute metrics on these and find an optional match […]. As the number of results seems to grow quicker than expected, this is impractical.

一般来说，如果您尝试 "generate all solutions" 并且您没有很好的理由去查看每一个（而且几乎从来没有），还有许多其他方法更可取，从直接尝试解决优化问题，到生成随机解决方案并查看它们，或者从某个子集生成解决方案（这似乎是您所做的）。

进一步阅读

跟进来自 OEIS 的参考文献导致了丰富的历史和理论。

  • 关于完整图的 1 分解和与循环调度的关系，Gelling（硕士论文），1973

  • On the number of 1-factorizations of the complete graph, Charles C Lindner, Eric Mendelsohn, Alexander Rosa (1974?) -- 这表明 nonisomorphic 1-随着 n 趋于无穷大，K2n 的因式分解趋于无穷大。

  • E.门德尔松和 A. Rosa。关于完全图的 1-分解的一些性质。国会数, 24 (1979): 739–752

  • E.门德尔松和 A. Rosa。完整图的一个因式分解：一项调查。 Journal of Graph Theory, 9 (1985): 43–65（早在 1985 年，这个确切的问题就被研究 well-enough 需要调查！）

  • 通过papers of Dinitiz:

  • Various One-Factorizations of Complete Graphs，作者：Gopal、Kothapalli、Venkaiah、Subramanian (2007)。一篇与这个问题相关的论文，有很多有用的参考资料。

  • W。 D. Wallis，组合设计简介，第二版 (2007)。第 10 章是 "One-Factorizations"，第 11 章是 "Applications of One-Factorizations"。两者都非常相关并且有很多有用的参考。

  • Charles J. Colbourn 和 Jeffrey H. Dinitz，组合设计手册，第二版（2007 年）。 金矿。 参见章节 VI.3 平衡锦标赛设计、VI.51 安排锦标赛、VII.5 图的因式分解（包括其部分 5.4 枚举和表格、5.5 的一些 1-因式分解完整图），VII.6 设计理论中的计算方法（6.2 穷举搜索）。最后一章参考：

    • [715] K12是如何计算出来的（"orderly algorithm"），一个回溯——上面提到的Dinitz-Garnick-McKay论文
    • [725] “在许多其他与因式分解相关的主题中，包含一种用于查找 K2n 的 1-因式分解的快速算法。” （"Room squares and related designs"、J. H. Dinitz 和 S. R. Stinson）
    • [1270]（P. Kaski 和 P. R. J. Östergård，One-factorizations of regular graphs of order 12, Electron. J. Comb. 12, Research Paper 2, 25 pp. (2005))
    • [1271] “包含电子形式的 10 阶完整图的 1 因式分解。” （P. Kaski 和 P. R. J. Östergård，代码和设计的分类算法，Springer，柏林，2006 年。）
    • [1860] “关于 K2n 的完美 1-因式分解的调查”（E. S. Seah，完全图的完美 one-factorizations——调查，Bull。 Inst. Combin. Appl. 1 (1991) 59–70)
    • [2107]“完整图的 1 分解调查，包括本章的大部分 material。” W. D. Wallis，One-factorizations of complete graphs，载于 Dinitz 和 Stinson（编），当代设计理论，1992
    • [2108] “一本关于图形 1 分解的书。” W. D. Wallis, "One-Factorizations", Kluwer, 多德雷赫特, 1997

一些其他的东西：