制作具有 1..N 范围内唯一数字对的插槽

Question

有N个数字。假设 N = 6

这里定义了一个范围，从1开始：[1,2,3,4,5,6]

我需要创建它们的唯一对，以便范围内的每个数字仅与另一个数字配对一次。

例如，可用的对是：

(1,2),(1,3),(1,4),(1,5),(1,6),
(2,3),(2,4),(2,5),(2,6),
(3,4),(3,5),(3,6),
(4,5),(4,6),
(5,6)

所以我们可以说对于 N 的值，将有 N*(N-1)/2 对。

对于N = 6，总对数为15。

现在，这些对需要放在插槽中，这样一个插槽只会使用一次数字。此外，任何一对都不能多次使用。

反例：

Slot 1 - (1,2),(3,4),(5,6)
Slot 2 - (1,3),(2,4),(5,6) - This is a wrong slot as (5,6) is already used in Slot 1
Slot 2 - (1,3),(2,6),(4,5) - Correct
Slot 3 - (1,4),(2,5),(3,6)
Slot 4 - (1,5),(2,3),(4,6)
Slot 5 - (1,6),(2,4),(3,5)

总共会有 S 个槽位，其中 S = N-1.

这里如果N = 6，则槽数=6 - 1 = 5.

问题

我找不到创建此类插槽的模式。我正在为此寻找一种算法。如果代码是可能的，我更喜欢 Python.

截至目前，将 N 视为偶数：6, 8, 12, ...

Answer 1

这是一个循环赛问题。

你可以使用circle method让每个人在几轮（槽位）中扮演团队中的任何其他成员（这是配对部分）。

对于 n = 10，你会看这个 snake-walk table:

 1  2  3  4  5  
10  9  8  7  6

插槽一的对由列定义：(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)

对于下一个插槽，将所有项目移动到一个“圆圈”中，除了 1：

 1 10  2  3  4  
 9  8  7  6  5

再次从列中读出对。

下一个广告位：

 1  9 10  2  3  
 8  7  6  5  4

...重复，直到您回到第一个插槽的配置。

只要您始终如一地应用此圆周移动，从哪种配置开始并不重要。只需将一个角值固定到位，而其他项则从一个槽到另一个槽环绕。

这是一个实现：

def getslots(n):
    for round in range(1, n):
        yield [(1, round + 1)] + [
              tuple(sorted(
                  ((top+round) % (n - 1) + 2, 
                  (n - 3 + round - top) % (n - 1) + 2)
               )) for top in range(n//2 - 1)]

如果您不关心一对中两个数字的顺序，则可以省略 tuple 和 sorted 调用。

制作具有 1..N 范围内唯一数字对的插槽

Make slots having unique pairs of numbers in the range 1..N

python

sorting

algorithm

logic

问题