Algorytm generowania listy modeli nawiasów w języku Python

Question

Próbuję utworzyć prostą funkcję rekursywną, która wygeneruje listę zagnieżdżonych list w języku Python. Wynik końcowy będzie reprezentował pojedynczy turniej turniejowy eliminacji. Mam nadzieję, że stworzenie takiej listy ułatwi mi generowanie tego, czego potrzebuję. Będzie to później wykorzystywane do tworzenia modeli meczów turniejowych.

Więc jeśli jest to turniej z 4 uczestników:

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

Turniej 7 uczestników:

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

Albo turniej z 8 uczestników:

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

I haven” t ma jeszcze klasę algorytmów (mam nadzieję, że klasa skończy się pomaganiem w takich rzeczach), więc nie jestem całkowicie upewnij się, jak podejść do tego problemu. Poniżej moja dotychczasowa próba.

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) 

Każda pomoc lub wyjaśnienie, jak się do tego podejść, zostanie bardzo doceniona!

Edit: Obecnie jestem wywołując funkcję tak:

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

Answer 1

Spróbuj tego:

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 

Zauważamy, że na wsporniku z 2^n graczy, suma każdej pary jest ten sam numer. Dla każdej pary prawy termin jest określany przez lewy element i głębokość rekurencji, więc możemy po prostu przejść przez generowanie głębokości tablicy. Zapamiętujemy uzupełnienia, aby nieco ulepszyć środowisko uruchomieniowe. Działa dla każdego m > 1, ponieważ przestaje powtarzać, gdy dopełnienie jest zbyt duże.

Zobacz go w akcji: http://ideone.com/26G1fB