分享程序员开发的那些事...
更新时间：2023-01-11 21:18:20
这是一个有趣的问题。在回答问题的过程中（基本上是在编写下面包含的程序，并在OEIS上查找顺序之后），我了解到该问题有一个名称和丰富的理论：您想要的是生成所有的 1-factorizations完整的图K 2k 。
This was an interesting question. In the process of answering it (basically after writing the program included below, and looking up the sequence on OEIS), I learned that the problem has a name and rich theory: what you want is to generate all 1-factorizations of the complete graph K2k.
让我们首先重申一下问题语言：
Let's first restate the problem in that language:
系统会为您提供数字k和大小为2k的列表（集合）L。我们可以将L视为完整图K 2k 的顶点集。
You are given a number k, and a list (set) L of size 2k. We can view L as the vertex set of a complete graph K2k.
一个 1因子（又称 perfect匹配）是将L划分为无序对（大小为2的集合）。也就是说，它是一组k对，其不相交联合为L。
A 1-factor (aka perfect matching) is a partition of L into unordered pairs (sets of size 2). That is, it is a set of k pairs, whose disjoint union is 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…。
Let S (called C in the question) denote the set of all pairs of elements of L. (In terms of the complete graph, if L is its vertex set, S is its edge set.) Note that S contains (2k choose 2) = k(2k-1) pairs. So for k = 0, 1, 2, 3, 4, 5, 6…, S has size 0, 1, 6, 15, 28, 45, 66….
一个 1因数分解是将S划分为若干个集合，每个集合本身都是一个1-因素（完美匹配）。请注意，由于每个匹配项都有k对，而S的大小为k（2k-1），因此分区的大小为2k-1（即由2k-1个匹配项组成）。
A 1-factorization is a partition of S into sets, each of which is itself a 1-factor (perfect matching). Note that as each of these matchings has k pairs, and S has size k(2k-1), the partition has size 2k-1 (i.e., is made of 2k-1 matchings).
换句话说，S（每对）的每个元素都恰好出现在1因式分解，L的每个元素在1因式分解的每个元素中恰好发生一次。
In other words, every element of S (every pair) occurs in exactly one element of the 1-factorization, and every element of L occurs exactly once in each element of the 1-factorization.
问题要求生成所有1因式分解。
The problem asks to generate all 1-factorizations.
让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…。
Let M denote the set of all 1-factors (all perfect matchings) of L. It is easy to prove that M contains (2k)!/(k!2^k) = 1×3×5×…×(2k-1) matchings. For k = 0, 1, 2, 3, 4, 5, 6…, the size of M is 1, 1, 3, 15, 105, 945, 10395….
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']
For example, calling perfect_matchings('abcdef') yields the 15 elements ['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'] as expected.
按照定义，1分解是将S分解为M中的元素。或者等效地，M的任何（2k-1）不相交元素形成1分解。这使自己有一个简单的回溯算法：
By definition, a 1-factorization is a partition of S into elements from M. Or equivalently, any (2k-1) disjoint elements of M form a 1-factorization. This lends itself to a straightforward backtracking algorithm:
在代码中：
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因式分解。我已经放置了执行此操作的完整程序这里。当k = 4（具体来说，列表'abcdefgh'）时，它将输出6240个1因子分解；完整的输出是此处。
If you call it with extend_matching_list(0, len(l) - 1) (after populating known_matchings), it generates all 1-factorizations. I've put the full program that does this here. With k=4 (specifically, the list 'abcdefgh'), it outputs 6240 1-factorizations; the full output is here.
在这一点上，我将序列1，6，6240输入OEIS，并发现了 OEIS A000438，序列1、1、6、6240、1225566720、252282619805368320，…。它表明，对于k = 6，解的数量≈2.5×10 17 意味着我们可以放弃生成所有解的希望。即使对于k = 5，≈10亿个解决方案（回想一下，我们正在尝试从| M | = 945匹配中找到2k-1 = 9个不相交集）也需要一些经过仔细优化的程序。
It was at this point that I fed the sequence 1, 6, 6240 into OEIS, and discovered OEIS A000438, sequence 1, 1, 6, 6240, 1225566720, 252282619805368320,…. It shows that for k=6, the number of solutions ≈2.5×1017 means that we can give up hope of generating all solutions. Even for k=5, the ≈1 billion solutions (recall that we're trying to find 2k-1=9 disjoint sets out of the |M|=945 matchings) will require some carefully optimized programs.
第一个优化（令人尴尬的是，我只有在稍后仔细查看k = 4的跟踪输出才意识到）是（在自然字典序法下） first的索引在分区中选择的em>匹配不能大于k-1的匹配数。这是因为S的字典顺序上的第一个元素（例如 ab ）仅出现在那些匹配中，并且如果我们晚于该匹配开始，则在任何其他匹配中都不会再找到它。
The first optimization (which, embarrassingly, I only realized later by looking closely at trace output for k=4) is that (under natural lexicographic numbering) the index of the first matching chosen in the partition cannot be greater than the number of matchings for k-1. This is because the lexicographically first element of S (like "ab") occurs only in those matchings, and if we start later than this one we'll never find it again in any other matching.
第二个优化来自以下事实：回溯计划的瓶颈通常是对当前候选人是否可接纳的测试。我们需要有效地测试不相交性：给定的匹配项（在我们的部分分解中）是否与所有先前匹配项的并集不相交。 （是否它的k对中的任何一个都是早先的匹配已经覆盖的对中的一个。）对于k = 5，事实证明S的大小（2k选择2）= 45小于64，所以我们可以紧凑地表示64位整数类型中的匹配项（毕竟是S的子集）：如果我们将对编号为0到44，则任何匹配项都可以由与元素相对应的位置处具有1的整数表示它包含了。然后对不相交性进行测试是对整数进行简单的按位运算：我们只需检查当前候选匹配的按位与和部分分解中先前匹配的累积并集（按位或）是否为零。
The second optimization comes from the fact that the bottleneck of a backtracking program is usually the testing for whether a current candidate is admissible. We need to test disjointness efficiently: whether a given matching (in our partial factorization) is disjoint with the union of all previous matchings. (Whether any of its k pairs is one of the pairs already covered by earlier matchings.) For k=5, it turns out that the size of S, which is (2k choose 2) = 45, is less than 64, so we can compactly represent a matching (which is after all a subset of S) in a 64-bit integer type: if we number the pairs as 0 to 44, then any matching can be represented by an integer having 1s in the positions corresponding to elements it contains. Then testing for disjointness is a simple bitwise operation on integers: we just check whether the bitwise-AND of the current candidate matching and the cumulative union (bitwise-OR) of previous matchings in our partial factorization is zero.
执行此操作的C ++程序是此处，仅回溯部分（专门针对k = 5）不需要任何C ++功能，因此它是此处提取为C程序。它可以在我的笔记本电脑上运行约4–5个小时，并找到所有1225566720 1个因式分解。
A C++ program that does this is 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. It runs in about 4–5 hours on my laptop, and finds all 1225566720 1-factorizations.
查看此问题的另一种方法是说M的两个元素如果它们相交（具有一对（共同的S元素））在它们之间具有优势，并且我们正在寻找M中的所有最大独立集。同样，解决该问题的最简单方法仍然可能是回溯（我们将编写相同的程序。）
Another way to look at this problem is to say that two elements of M have an edge between them if they intersect (have a pair (element of S) in common), and that we're looking for all maximum independent set in M. Again, the simplest way to solve that problem would still probably be backtracking (we'd write the same program).
通过利用问题的对称性，我们的程序可以变得更加高效：例如，我们可以选择任何匹配项作为我们在1因式分解中的第一个1因数（然后通过重新标记生成其余因数，请注意避免重复）。这是计算K 12 （当前记录）的1分解次数的方式。
Our programs can be made quite a lot more efficient by exploiting the symmetry in our problem: for example we could pick any matching as our first 1-factor in the 1-factorization (and then generate the rest by relabelling, being careful not to avoid duplicates). This is how the number of 1-factorizations for K12 (the current record) was calculated.
关于生成所有解决方案的智慧的注释
在《计算机编程的艺术》（第4A卷）中，在第7.2.1.2节生成所有排列的最后，Knuth提出了以下重要建议：
In The Art of Computer Programming Volume 4A, at the end of section 7.2.1.2 Generating All Permutations, Knuth has this important piece of advice:
在进行置换之前，请三思而后行。在本节中，我们已经看到了几种有吸引力的置换生成算法，但是众所周知，有许多算法可以找到无需即可满足特定目的的***置换。例如，[…]在顺序存储中排列记录的***方法[…]仅需要O（ n log n ）个步骤。 […] 赋值问题，该问题询问如何置换方阵的列，以使对角元素的总和最大化[…]最多可以解决O（ n 3 ）操作，因此使用命令 n 的方法是愚蠢的！除非 n 很小。即使在诸如旅行销售代表问题的情况下，当没有有效的算法被知道时，我们通常可以找到比检查每个可能的解决方案更好的方法。当有充分的理由单独查看每个排列时，***使用排列生成。
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.
这似乎是这里发生的情况（摘自问题下方的注释）：
This is what seems to have happened here (from the comments below the question):
我想计算所有解决方案以对这些解决方案运行不同的属性指标并找到可选的匹配项[…] 。由于结果的数量似乎比预期的增长快，所以这是不切实际的。
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.
通常，如果您要全部生成解决方案，并且您没有一个很好的理由来查看每个解决方案（而且几乎从来没有这样做过），还有许多其他方法是更可取的，从直接尝试解决优化问题到生成随机解并查找
Generally, if you're trying to "generate all solutions" and you don't have a very good reason for looking at each one (and one almost never does), there are many other approaches that are preferable, ranging from directly trying to solve an optimization problem, to generating random solutions and looking at them, or generating solutions from some subset (which is what you seem to have done).
进一步的工作，或者从某些子集中生成解决方案。阅读
从 OEIS 导致了丰富的历史和理论。
Following up references from OEIS led to a rich history and theory.
关于完整图的一阶分解以及与倒数的关系robin schedules ，Gelling（文学硕士，1973年）
On 1-factorizations of the complete graph and the relationship to round robin schedules, Gelling (M. A. Thesis), 1973
关于完整图的1分解数 ，Charles C Lindner，Eric Mendelsohn，Alexander Rosa（1974？）–这表明 2n 上的>非同构一阶分解变为无穷大，而n变为无穷大。
On the number of 1-factorizations of the complete graph, Charles C Lindner, Eric Mendelsohn, Alexander Rosa (1974?) -- this shows that the number of nonisomorphic 1-factorizations on K2n goes to infinity as n goes to infinity.
E。门德尔松和罗莎（A. Rosa）。关于完备图的1-分解的一些性质。大会Numer，24（1979）：739–752
E. Mendelsohn and A. Rosa. On some properties of 1-factorizations of complete graphs. Congr. Numer, 24 (1979): 739–752
E。门德尔松和罗莎（A. Rosa）。完整图形的一个因式分解：一项调查。 Journal of Graph Theory，9（1985）：43–65（早在1985年，就已经对这一确切的问题进行了充分研究，需要进行调查！）
E. Mendelsohn and A. Rosa. One factorizations of the complete graph: A survey. Journal of Graph Theory, 9 (1985): 43–65 (As long ago as 1985, this exact question was studied well-enough to need a survey!)
通过 Dinitiz的论文：
各种因素Gopal，Kothapalli，Venkaiah，Subramanian撰写的Complete Graphs 。与此问题相关的论文，并且有很多有用的参考文献。
Various One-Factorizations of Complete Graphs by Gopal, Kothapalli, Venkaiah, Subramanian (2007). A paper that is relevant to this question, and has many useful references.
W。 D. Wallis，《组合设计简介》，第二版（2007年）。第10章是一要素化，第11章是一要素化的应用。两者都很相关，并且有很多有用的参考。
W. D. Wallis, Introduction to Combinatorial Designs, Second Edition (2007). Chapter 10 is "One-Factorizations", Chapter 11 is "Applications of One-Factorizations". Both are very relevant and have many useful references.
Charles J. Colbourn和Jeffrey H. Dinitz，《组合设计手册》第二版（2007年）。 金矿。请参见第VI.3节平衡锦标赛设计，VI.51安排锦标赛，VII.5图形分解（包括其5.4枚举和表格，5.5完整图形的某些1-分解）一章。 ，VII.6设计理论中的计算方法（6.2详尽搜索）。最后一章引用：
Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Second Edition (2007). A goldmine. See chapters VI.3 Balanced Tournament Designs, VI.51 Scheduling a Tournament, VII.5 Factorizations of Graphs (including its sections 5.4 Enumeration and Tables, 5.5 Some 1-Factorizations of Complete Graphs), VII.6 Computational Methods in Design Theory (6.2 Exhaustive Search). This last chapter references:
有些其他内容：
* 图的因果分解。这看起来像一本好书。弗兰克·哈拉里（Frank Harary）预测，图论将发展得如此之快，以至于他的《图论》（ Graph Theory ）的每一章最终都会扩展成为一本书。他是对的。这本书是他的第9章因式分解的扩展。这个特定的主题（完整图的1分解）没有很多，但是在第4章（定理4.1.1）中有一个证明K 2n 总是具有1分解。
*Factors and Factorizations of Graphs by Jin Akiyama and Mikio Kano (2007). This looks like a great book. "Frank Harary predicted that graph theory will grow so much that each chapter of his book Graph Theory will eventually expand to become a book on its own. He was right. This book is an expansion of his Chapter 9, Factorization." There's not much about this particular topic (1-factorizations of complete graphs), but there is a proof in Chapter 4 (Theorem 4.1.1) that K2n always has a 1-factorization.
特殊类型的1分解的论文：
Papers on special types of 1-factorizations:
另请参见 OEIS索引[与比赛相关的序列]条目。