是否有任何算法可以在小于 O(n!) 的时间内解决以下问题？
Are there any algorithm that solves the following problem in time less than O(n!)?
有没有什么算法可以像多项式时间一样在小于O(n!)的时间内解决下面的问题？
不然这道题，像NP题一样，没有人发现什么多项式时间算法吗？
输入：n（元素个数）
输出：两个的所有组合的列表，其中，从列表顶部开始，n/2的每个组合单元必须具有所有元素。
示例 1
Input: n=4
Output:
[0, 1], [2, 3],
[0, 2], [1, 3],
[0, 3], [1, 2]
示例 2
Input: n=8
Output:
[0, 1], [2, 3], [4, 5], [6, 7],
[0, 2], [1, 3], [4, 6], [5, 7],
[0, 3], [1, 2], [4, 7], [5, 6],
[0, 4], [1, 5], [2, 6], [3, 7],
[0, 5], [1, 4], [2, 7], [3, 6],
[0, 6], [1, 7], [2, 4], [3, 5],
[0, 7], [1, 6], [2, 5], [3, 4]
P.S。
以下回答不符合要求。
前两个(=n/2)对([0, 1], [0, 2])没有“3”，所以答案不满足条件where“0”和“1”，“ 2", "3" 必须在前两对。
>>> n=4
>>> for i in range(0, n-1):
... for j in range(i+1,n):
... print( [i, j] )
...
[0, 1]
[0, 2]
[0, 3]
[1, 2]
[1, 3]
[2, 3]
是的，这个问题可以用二次方的时间来解决。显式构建这些配对并不难。
考虑在中间多一个点的正则 (n-1) 边形非常有帮助。然后取通过 (n-1) 个端点之一和中点的线，并选择由这条线的对称性给出的线对。
正如我在评论中所说，这似乎是一种（宽松的）体育联盟调度问题。如果我理解你的要求，可以总结如下：
给定一个正偶数 N 生成一组 n/2 个具有以下性质的配对“轮”：
- 配对是一对两个不同的整数
[a, b]，其中 a 和 b 是来自 0..n-1 和 a < b 的整数。
- 一轮由
n/2 对组成，因此来自 0..n-1 的每个元素在该轮的一对中只出现一次，并且
- 所有配对在所有回合中都是唯一的（即没有配对在完整解决方案中出现超过一次）。
假设这是您问题的正确表述，那么答案是
是的，这可以在 O(n^2).
中完成
此外，不仅可以做到，还有一个简单的方法可以解决任何偶数N：
第一轮，制作n-1对，用从左到右从0到(n/2)-1的整数填充对的第一个元素。这是 N=8:
的查找方式
[0, ], [1, ], [2, ], [3, ]
然后，将第二个元素填入(n/2)到n-1，但是从右到左：
[0, 7], [1, 6], [2, 5], [3, 4]
你的第一轮到此结束。
对于下一轮，复制第一轮，但将 0 保持在同一位置，将剩余的左侧元素向上移动列表，将右侧元素向下移动列表。当一个元素到达列表的末尾时，反转方向并将它们从第一个元素交换到第二个元素（反之亦然）：
----------------------->
[0, 7], [1, 6], [2, 5], [3, 4]
<-----------------------
变成
----------------------->
[0, 6], [7, 5], [1, 4], [2, 3]
<-----------------------
现在你只需继续这个过程，直到你有 N/2 个回合：
[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [7, 5], [1, 4], [2, 3]
[0, 5], [6, 4], [7, 3], [1, 2]
[0, 4], [5, 3], [6, 2], [7, 1]
最后交换第一个元素恰好大于第二个元素的所有配对：
[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [5, 7], [1, 4], [2, 3]
[0, 5], [4, 6], [3, 7], [1, 2]
[0, 4], [3, 5], [2, 6], [1, 7]
如果您检查此解决方案，您会发现它满足所有限制条件。此解决方案适用于 N 的任何偶数值，并且显然在 O(n^2) 时间内运行。
有没有什么算法可以像多项式时间一样在小于O(n!)的时间内解决下面的问题？ 不然这道题，像NP题一样，没有人发现什么多项式时间算法吗？
输入：n（元素个数）
输出：两个的所有组合的列表，其中，从列表顶部开始，n/2的每个组合单元必须具有所有元素。
示例 1
Input: n=4
Output:
[0, 1], [2, 3],
[0, 2], [1, 3],
[0, 3], [1, 2]
示例 2
Input: n=8
Output:
[0, 1], [2, 3], [4, 5], [6, 7],
[0, 2], [1, 3], [4, 6], [5, 7],
[0, 3], [1, 2], [4, 7], [5, 6],
[0, 4], [1, 5], [2, 6], [3, 7],
[0, 5], [1, 4], [2, 7], [3, 6],
[0, 6], [1, 7], [2, 4], [3, 5],
[0, 7], [1, 6], [2, 5], [3, 4]
P.S。 以下回答不符合要求。 前两个(=n/2)对([0, 1], [0, 2])没有“3”，所以答案不满足条件where“0”和“1”，“ 2", "3" 必须在前两对。
>>> n=4
>>> for i in range(0, n-1):
... for j in range(i+1,n):
... print( [i, j] )
...
[0, 1]
[0, 2]
[0, 3]
[1, 2]
[1, 3]
[2, 3]
是的，这个问题可以用二次方的时间来解决。显式构建这些配对并不难。
考虑在中间多一个点的正则 (n-1) 边形非常有帮助。然后取通过 (n-1) 个端点之一和中点的线，并选择由这条线的对称性给出的线对。
正如我在评论中所说，这似乎是一种（宽松的）体育联盟调度问题。如果我理解你的要求，可以总结如下：
给定一个正偶数 N 生成一组 n/2 个具有以下性质的配对“轮”：
- 配对是一对两个不同的整数
[a, b]，其中 a 和 b 是来自0..n-1和a < b的整数。 - 一轮由
n/2对组成，因此来自0..n-1的每个元素在该轮的一对中只出现一次，并且 - 所有配对在所有回合中都是唯一的（即没有配对在完整解决方案中出现超过一次）。
假设这是您问题的正确表述，那么答案是
是的，这可以在 O(n^2).
此外，不仅可以做到，还有一个简单的方法可以解决任何偶数N：
第一轮，制作n-1对，用从左到右从0到(n/2)-1的整数填充对的第一个元素。这是 N=8:
[0, ], [1, ], [2, ], [3, ]
然后，将第二个元素填入(n/2)到n-1，但是从右到左：
[0, 7], [1, 6], [2, 5], [3, 4]
你的第一轮到此结束。
对于下一轮，复制第一轮，但将 0 保持在同一位置，将剩余的左侧元素向上移动列表，将右侧元素向下移动列表。当一个元素到达列表的末尾时，反转方向并将它们从第一个元素交换到第二个元素（反之亦然）：
----------------------->
[0, 7], [1, 6], [2, 5], [3, 4]
<-----------------------
变成
----------------------->
[0, 6], [7, 5], [1, 4], [2, 3]
<-----------------------
现在你只需继续这个过程，直到你有 N/2 个回合：
[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [7, 5], [1, 4], [2, 3]
[0, 5], [6, 4], [7, 3], [1, 2]
[0, 4], [5, 3], [6, 2], [7, 1]
最后交换第一个元素恰好大于第二个元素的所有配对：
[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [5, 7], [1, 4], [2, 3]
[0, 5], [4, 6], [3, 7], [1, 2]
[0, 4], [3, 5], [2, 6], [1, 7]
如果您检查此解决方案，您会发现它满足所有限制条件。此解决方案适用于 N 的任何偶数值，并且显然在 O(n^2) 时间内运行。