<p>首先,从列表中获取所有对的自然方法是:</p>
<pre><code>>>> N = 10
>>> input_list = range(N)
>>> [(a,b) for a, b in zip(input_list[::2], input_list[1::2])]
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9)]
</code></pre>
<p>如果你想生成所有这样的对,我会做一些类似的事情(下面我称之为案例1):</p>
^{pr2}$
<p>如果这样的话,这将区分成对的顺序(例如,(1,4)与(4,1)不同),并且认为成对的顺序是有意义的。因此,如果在添加到集合之前对这些对和一组对进行排序:</p>
<pre><code>>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = sorted([tuple(sorted((a,b))) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(tuple(pairs))
</code></pre>
<p>这不是一个有效的算法(下面我称之为案例3),但对于N值较小的情况,它可以工作。在</p>
<p>对于N=6,使用排序方法。在</p>
<pre><code>set([((0, 4), (1, 3), (2, 5)),
((0, 4), (1, 5), (2, 3)),
((0, 1), (2, 3), (4, 5)),
((0, 3), (1, 5), (2, 4)),
((0, 2), (1, 5), (3, 4)),
((0, 4), (1, 2), (3, 5)),
((0, 3), (1, 4), (2, 5)),
((0, 1), (2, 4), (3, 5)),
((0, 5), (1, 4), (2, 3)),
((0, 5), (1, 2), (3, 4)),
((0, 2), (1, 3), (4, 5)),
((0, 3), (1, 2), (4, 5)),
((0, 2), (1, 4), (3, 5)),
((0, 1), (2, 5), (3, 4)),
((0, 5), (1, 3), (2, 4))])
</code></pre>
<p>注意,解空间呈指数级增长;(例如,对于N=6,其15;对于N=8,其105;对于N=10,其945;对于N=46,其945将为25373791335626257947657609375~2.5x10<sup>28</sup>)。在</p>
<h2>编辑:人们批评O(N!),但所需的解决方案会增长为O(N!)在</h2>
<p>这个问题要求将N个元素的列表(假设所有元素都是不同的)分成一组(N/2)对,不仅这样做一次,而且生成这些对的<strong>所有</strong>集。这个答案是唯一的答案。是的,它是指数级的慢,而且对于N=46完全不可行。所以我用N=10。在</p>
<p>对这个问题有三种合理的解释:</p>
<p><strong>情况1:</strong>排序关系到元组中一对内的排序(例如,函数参数不是对称的),而且在一组对中对的顺序也很重要,那么我们将得到N!答案中数字配对的方法。这意味着在这种情况下,对(0,1)和(1,0)都被认为是不同的,对于N=4的情况,我们认为<code>{(0,1), (2,3)}</code>与{<cd2>}不同。在</p>
<p><strong>案例2:</strong>一对中的排序很重要,但在一组配对中,顺序是不相关的。这意味着我们将(0,1)和(1,0)视为不同的对,但是考虑(对于N=4的情况)集合<code>{(0,1),(2,3)}</code>与集合{<cd4>}是相同的,不需要同时考虑这两个。在这种情况下,我们将有N!/(N/2)!配对,就像任何给定的集合有(N/2)!不同的顺序。(我没有在上面明确给出这个;只是停止对元组进行排序)。在</p>
<p><strong>案例3:</strong>排序在一对和一组配对中都是不相关的。这意味着我们将(0,1)和(1,0)视为同一对(函数参数是对称的),因此我们将得到N!/(N/2)!&;2^(N/2))对集(<code>factorial(N)/(factorial(N/2)*2**(N/2))</code>)。每个组合中的每个(N/2)对都有两个内部顺序。在</p>
<p>因此,根据问题的措辞,我们应该:</p>
<pre><code> Case 1 | Case 2 | Case 3
N N! | N!/(N/2)! | N!/((N/2)! 2^(N/2))
6 720 | 120 | 15
8 40320 | 1680 | 105
10 3628800 | 30240 | 945
46 5.5x10^57 | 2.1x10^35 | 2x10^28
</code></pre>
<p>对于3的情况,排序算法比3的情况要慢得多。然而,我的答案在渐近表示法中仍然是最优的,因为偶数情况3在其渐近运行时间上是阶乘的,并且对于N~46完全不可行。如果你必须在案例3的可行性极限(N~16)下做一个问题大小(例如,需要生成518918400.0对),这种迭代所有N的解决方案是可行的!排列、排序和丢弃重复项是次优的。在</p>