Algorithmus zum Generieren einer Klammermodellliste in Python

Question

Ich versuche, eine einfache rekursive Funktion zu erstellen, die eine Liste von verschachtelten Listen in Python generiert. Das Endergebnis wird eine Ausscheidungsrunde darstellen. Ich hoffe, dass das Erstellen einer solchen Liste es mir leicht macht, das zu generieren, was ich brauche. Dies wird später verwendet, um Modelle für Turnierspiele zu erstellen.

Also, wenn es ein Turnier von 4 Teilnehmern ist:

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

Turnier von 7 Teilnehmern:

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

Oder ein Turnier von 8 Teilnehmern:

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

I haven‘ Ich hatte noch eine Klasse von Algorithmen (ich hoffe, dass die Klasse am Ende mit solchen Dingen helfen wird), also bin ich nicht vollständig sicher, wie Sie dieses Problem angehen. Unten ist mein Versuch soweit.

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) 

Jede Hilfe oder Erklärung, wie man sich nähert, würde sehr geschätzt!

Edit: Derzeit Ich rufe die Funktion wie folgt aus:

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

Answer 1

Try this:

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 

Wir bemerken, dass mit 2^n Spieler für eine Klammer, die Summe von jedem Paar ist die gleiche Nummer. Für jedes Paar wird der rechte Ausdruck durch das linke Element und die Tiefe der Rekursion bestimmt, so dass wir einfach fortfahren können, indem wir zuerst die Array-Tiefe erzeugen. Wir notieren die Ergänzungen, um die Laufzeit ein wenig zu verbessern. Es funktioniert für jede , wie es zu rekursiv stoppt, sobald das Komplement zu groß ist.

Sehen sie in Aktion: http://ideone.com/26G1fB