如何在给定k和特定条件的比赛中配对

Question

面试时有人问我。我没有做笔记，所以问题描述可能有点模糊。你知道吗

数字是锦标赛中的排名。你知道吗

k=1, return (1, 2) 
k=2, return ((1, 4), (2, 3)) 
k=3, return (((1, 8), (4, 5)), ((2, 7), (3, 6)))
k=4, return ((((1, 16), (8, 9)), ((4, 13), (5, 12))), (((2, 15), (7, 10)), (3, 14), (6, 11))))

最小的等级应始终与最大的等级配对。例如，k=3 (((1, 8), (4, 5)), ((2, 7), (3, 6))) -> ((1, 4), (2, 3)) -> (1, 2) -> 1 (winner)

我认为暴力解决方案是创建一个给定k的数字列表，并通过增加左右索引在最大数和最小数之间配对。但一旦配对完成，我应该可以进一步配对。例如，当k=3时，我可以创建一个列表：[1, 2, 3, 4, 5, 6, 7, 8]，并创建一个成对列表：[(1, 8), (2, 7), (3, 6), (4, 5)]。在那之后，我应该能够再次配对到这个：[((1, 8), (4, 5)), ((2, 7), (3, 6))]

在我把两个数字配对后，我不能想出一个嵌套的配对规则，它可以应用于任何给定的k数。你知道吗

编辑：给出K。使用k，您可以创建一个从1到2**k的数字列表。因此，如果k=3，数字列表将是[1，2，3，4，5，6，7，8]。正如我上面提到的，这个数字代表一个等级。所以“1”是锦标赛后的赢家。因为“1”是赢家（最小的数字），“1”应该和“8”（最下面的数字和最大的数字）配对。如下（2，7），（3，6），（4，5）。但既然这是一场锦标赛，你就希望每对选手中的一个胜利者能再次比赛。因为条件是（第一小，第一大），（第二小，第二大）…，所以应该配对（（1，8），（4，5））和（（2，7），（3，6））。（（1，8），（4，5））->；（1，4），（（2，7），（3，6））->；（2，3）=>；（（1，4），（2，3））=>；（1，2）=>；1（优胜者）

这个问题的目标是将给定k和某个条件的数字（通过嵌套的元组或列表）配对（最小1，最大1），（最小2，最大2）。你知道吗

我尝试了暴力解决方案，我想不出如何在给定k的嵌套循环中配对。我还想到了使用二叉树和递归方法，我应该知道如何在给定k和特定条件下配对，这就是我无法前进的地方。你知道吗

Answer 1

哇，希望面试官在解释问题陈述方面做得更好

也许这就是你想要的

def get_pairs(L):
    L = sorted(L)
    middle = len(L)//2
    result=list(zip(L[:middle],L[:middle-1:-1]))
    if len(result) > 2:
        return get_pairs(result)
    return result

print get_pairs(range(1,5)) #k=2 ???    
print get_pairs(range(1,9)) #k=3 ???
print get_pairs(range(1,17) #k=4 ???

啊哈，我想我知道了（wtf k是什么，它是怎么联系起来的）。。你知道吗

def get_pairs_for_rank(k):
    return get_pairs(range(1,2**k+1))