Algoritmo per la generazione di un elenco di modelli di parentesi in Python

Question

Sto provando a creare una semplice funzione ricorsiva che generi un elenco di elenchi nidificati in Python. Il risultato finale rappresenterà una singola parentesi torneo di eliminazione. Spero che la creazione di una lista come questa mi consenta di generare ciò di cui ho bisogno. Questo verrà in seguito utilizzato per creare modelli per le partite del torneo.

Quindi, se c'è un torneo di 4 partecipanti:

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

Torneo di 7 partecipanti:

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

o un torneo di 8 partecipanti:

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

Mi rifugio' Ho ancora una classe di algoritmi (spero che la classe finirà per aiutare con cose come questa) quindi non sono completamente sicuro come affrontare questo problema. Di seguito è il mio tentativo finora.

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) 

Qualsiasi aiuto o spiegazione su come avvicinarsi a questo sarebbe molto apprezzato!

Edit: Attualmente sto chiamando la funzione come questa:

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

Answer 1

Prova questo:

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 

Notiamo che per una staffa con i giocatori di 2^n, la somma di ogni coppia è lo stesso numero Per ogni coppia, il termine corretto è determinato dall'elemento sinistro e dalla profondità della ricorsione, quindi possiamo procedere generando prima la profondità dell'array. Memorizziamo i complementi per migliorare un po 'il tempo di esecuzione. Funziona con qualsiasi m > 1 poiché si arresta in modo ricorrente una volta che il complemento è troppo grande.

vederlo in azione: http://ideone.com/26G1fB