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 に答える