我正在尝试创建一个简单的递归函数,它将在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
试试这个:
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
这是不正确的。 2 应该在括号的底部...