1

是否有任何算法可以在小于 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]

PS以下答案不符合要求。前两个 (= n/2) 对 ([0, 1], [0, 2]) 没有“3”，因此答案不满足“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]
4

2 回答 2

1

是的，这个问题可以在二次时间内解决。明确地构建这些配对并不难。

考虑一个中间有一个额外点的常规 (n-1) 边形非常有帮助。然后通过（n-1）个端点之一和中点取线，并选择由这条线的对称性给出的对。

于 2021-11-30T16:45:02.290 回答
1

正如我在评论中所说，这似乎是一种（宽松的）体育联赛日程安排问题。如果我理解您的要求，可以总结如下：

给定一个正偶数N，生成一组 n/2“轮”配对，具有以下性质：

  1. 配对是一对两个不同的整数[a, b]，使得 a 和 b 是来自0..n-1和的整数a < b。
  2. 一轮由n/2配对组成，因此来自的每个元素0..n-1在该轮的配对中恰好出现一次，并且
  3. 所有配对在所有轮次中都是唯一的（即没有配对在完整的解决方案中出现多次）。

假设这是您问题的正确表述，那么答案是

是的，这可以在O(n^2).

此外，不仅可以做到，还有一种简单的方法可以解决任何偶数 N 的问题：

对于第一轮，制作 n-1 对，用从左到右的整数填充对的第一个0元素(n/2)-1。这将如何寻找N=8：

[0, ], [1, ], [2, ], [3, ]

(n/2)然后，用to填充第二个元素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)及时运行。

于 2021-11-30T20:13:35.190 回答