在Python中生成括号模型列表的算法 [英] Algorithm for generating a bracket model list in Python

问题描述

我正在尝试创建一个简单的递归函数，该函数将在Python中生成嵌套列表的列表.最终结果将代表一个淘汰赛.我希望创建这样的列表可以使我轻松生成所需的内容.稍后将用于创建比赛的模型.

I'm trying to make a simple recursive function that will generate a list of nested lists in Python. The end result will represent a single elimination tournament bracket. I'm hoping that creating a list like this will make it easy for me to generate what I need. This will later be used to create models for tournament matches.

因此，如果有4名参与者参加的比赛:

So if there is a tournament of 4 participants:

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

7名参与者的比赛:

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

或8名参赛者参加的比赛:

Or a tournament of 8 participants:

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

我还没有算法类(我希望该类最终可以帮助此类事情)，所以我不确定如何解决这个问题.这是我到目前为止的尝试.

I haven't had an algorithms class yet (I'm hoping the class will end up helping with things like this) so I'm not completely sure how to approach this problem. Below is my attempt so far.

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)

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

Any help or explanation on how to approach this would be greatly appreciated!

目前，我正在这样调用函数:

Currently I am calling the function like this:

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 ，因为补码过大会停止递归.

We notice that for a bracket with 2^n players, the sum of every pair is the same number. For every pair, the right term is determined by the left element and the depth of the recursion, so we can just proceed by generating the array depth first. We memoize the complements to improve runtime just a bit. It works for any m > 1 as it stops recursing once the complement is too large.

查看实际运行情况: http://ideone.com/26G1fB

这篇关于在Python中生成括号模型列表的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！