7

我正在尝试制作一个简单的递归函数，它将在 Python 中生成嵌套列表的列表。最终结果将代表一个单场淘汰的锦标赛括号。我希望创建这样的列表能让我轻松生成所需的内容。这稍后将用于创建锦标赛比赛的模型。

因此，如果有 4 人参加的锦标赛：

[[1,4],[2,3]]

7人参赛：

[[1,[4,5]],[[2,7],[3,6]]]

或 8 人参加的锦标赛：

[[[1,8],[4,5]],[[2,7],[3,6]]]

我还没有一个算法课（我希望这个课最终会帮助解决这样的事情）所以我不完全确定如何解决这个问题。以下是我迄今为止的尝试。

def decide_rounds(list_to_fill, player_nums):
    if len(player_nums) < 3:
        for num in player_nums:
            list_to_fill.append(num)
        return

    left = []
    decide_rounds(left, ??????) #Tried passing various things to these with no avail.
    list_to_fill.append(left)
    right = []
    decide_rounds(right, ???????)
    list_to_fill.append(right)

任何有关如何解决此问题的帮助或解释将不胜感激！

编辑：目前我正在调用这样的函数：

rounds = []
decide_rounds(rounds, range(1, size +1))
print rounds
4

1 回答 1

8

试试这个：

def divide(arr, depth, m):
    if len(complements) <= depth:
        complements.append(2 ** (depth + 2) + 1)
    complement = complements[depth]
    for i in range(2):
        if complement - arr[i] <= m:
            arr[i] = [arr[i], complement - arr[i]]
            divide(arr[i], depth + 1, m)

m = int(raw_input())

arr = [1, 2]
complements = []

divide(arr, 0, m)
print arr

我们注意到，对于一个有 2^n 个玩家的括号，每对的总和是相同的数字。对于每一对，右项由左元素和递归深度决定，所以我们可以先生成数组深度。我们记住补语以稍微改善运行时间。它适用于任何人m > 1，因为一旦补码太大，它就会停止递归。

在行动中看到它：http: //ideone.com/26G1fB

于 2012-12-10T01:35:28.943 回答