Generate Parentheses

Q: Jaka jest złożoność czasowa generowania nawiasów?

Algorytm z nawrotami generuje C(n) = (2n)! / ((n+1)! n!) ciągów, czyli liczbę Catalana, która rośnie jak 4^n / (n^1.5 √π) . Zbudowanie i skopiowanie każdego z nich zajmuje O(n) , więc czas działania wynosi O(4^n / √n) . Dodatkowa pamięć wynosi O(n) na bieżący ciąg i stos wywołań, a do tego dochodzi pamięć na wynik.

Q: Ile jest poprawnych ciągów nawiasów dla n par?

n-ta liczba Catalana: 1, 2, 5, 14, 42, 132, 429 i 1,430 dla n od 1 do 8. Każdy poprawnie utworzony ciąg dzieli się na ( A ) B, gdzie to ) pasuje do pierwszego ( , a A i B mają po n - 1 parach. Sumowanie względem rozmiaru A daje rekurencję Catalana.

Q: Czy problem generowania nawiasów można rozwiązać bez rekurencji?

Tak. Przechowuj stos częściowych stanów, z których każdy jest ciągiem znaków zawierającym dwa liczniki, i rozszerzaj każdy stan zgodnie z tymi samymi dwiema regułami. Umieść rozszerzenie ) na stosie przed rozszerzeniem ( , aby najpierw zdjąć ze stosu to dla ( , a wynik pozostał posortowany.

ŚrednieNawroty Rekurencja

+10

Ciąg nawiasów jest poprawnie zbudowany, gdy czytany od lewej do prawej licznik ) nigdy nie wyprzedza licznika (, a na końcu oba liczniki są równe. Zatem (())() jest poprawnie zbudowany, a ())( nie: jego trzeci znak zamyka parę, która nigdy nie została otwarta.

Dla danej liczby całkowitej n zwróć każdy poprawnie zbudowany ciąg zawierający n nawiasów otwierających i n nawiasów zamykających, posortowany w porządku leksykograficznym, w którym ( występuje przed ).

Funkcja

generateParenthesis(n: integer) → string-array

ninteger: liczba par nawiasów
Zwracastring-array: każdy poprawnie utworzony ciąg n par, w porządku leksykograficznym

Ograniczenia

1 ≤ n ≤ 8
Dla n = 8 odpowiedź obejmuje 1,430 ciągów znaków.

Przykłady

Wejście: n = 3
Wyjście: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Wyjaśnienie: Trzy pary tworzą pięć poprawnie uformowanych ciągów. ((())) otwiera najpierw wszystkie trzy, więc jest sortowany jako pierwszy; ()()() od razu zamyka każdą parę i zajmuje ostatnie miejsce.

Wejście: n = 1
Wyjście: ["()"]
Wyjaśnienie: Jedna para tworzy jeden poprawny ciąg znaków. Jedyny inny układ, )(, zamyka nawias, zanim cokolwiek zostanie otwarte.

Pytanie dodatkowe

Czy potrafisz policzyć poprawnie zbudowane ciągi dla n par, nie generując ich?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Niewiele ciągów o długości 2n jest poprawnie zbudowanych: 1,430 z 65,536 dla n = 8. Buduj każdy ciąg od lewej do prawej i dodawaj znak tylko wtedy, gdy prefiks można jeszcze dokończyć. Decydują o tym dwa liczniki, a wypróbowanie ( przed ) sprawia, że ciągi są posortowane.

Utwórz każdy ciąg znaków, a następnie go sprawdź

Intuicja

Wypełnij 2n pozycji wszystkimi kombinacjami ( i ), czyli 4^n ciągami, a następnie zachowaj te poprawne. Aby sprawdzić ciąg, przejdź przez niego, śledząc bilans: dodaj 1 za ( i odejmij 1 za ). Ciąg jest poprawny, jeśli bilans nigdy nie spada poniżej 0 i na końcu wynosi 0. Umieszczając ( przed ) na każdej pozycji, otrzymasz ciągi w kolejności sortowania.

Sprawdzenie każdego ciągu kosztuje O(n). Dla n = 8 oznacza to 65 536 ciągów i 1 430 poprawnych wyników, więc około 98% pracy idzie na marne, a liczba ciągów rośnie czterokrotnie z każdą dodatkową parą.

Algorytm

Utrzymuj bufor o długości 2n znaków i listę odpowiedzi.
fill(pos): jeśli pos jest równe 2n, zapisz bufor, jeśli jest poprawnie sformowany.
W przeciwnym razie umieść ( na pozycji pos i wywołaj fill(pos + 1), a następnie umieść tam ) i wywołaj tę funkcję ponownie.
Aby sprawdzić poprawność, dodawaj 1 za każdy znak ( i odejmuj 1 za każdy znak ). Odrzuć wynik, gdy bilans spadnie poniżej 0 lub nie zakończy się na 0.
Wywołaj fill(0) i zwróć zapisane ciągi.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Prześledź wstecz liczbę nawiasów otwierających i zamykających

Intuicja

Przenieś sprawdzenie do budowania. Prefiks może rozwinąć się w poprawny ciąg dokładnie wtedy, gdy używa co najwyżej n znaków ( i nigdy nie ma więcej znaków ) niż (. Zatem ( jest dozwolony, gdy opened < n, a ) — gdy closed < opened. Przy długości 2n obie liczby wynoszą n, a ciąg jest poprawny i nie ma już nic do sprawdzania.

Żadna odpowiedź nie zostanie pominięta, ponieważ każdy prefiks poprawnego ciągu spełnia obie reguły. Żadna gałąź nie jest niepotrzebna: dla n = 2 gałąź (( może tylko dwa razy się zamknąć, dając (()), a gałąź () może tylko otworzyć i zamknąć, dając ()(). Każdy ciąg odpowiada jednej ścieżce w drzewie, więc pojawia się raz, a gałąź ( jest odwiedzana jako pierwsza, więc wynik jest posortowany.

Każdy liść jest odpowiedzią, więc nakład pracy jest proporcjonalny do rozmiaru wyniku: O(4^n / √n).

Algorytm

Utrzymuj budowany ciąg znaków i dwa liczniki: opened oraz closed, oba ustawione na 0.
Jeśli ciąg znaków ma długość 2n, zapisz jego kopię i zakończ.
Jeśli opened < n, dodaj (, wykonaj rekurencję z opened + 1 i usuń ten znak.
Jeśli closed < opened, dodaj ), wykonaj rekurencję z closed + 1 i usuń ten znak.
Zacznij od pustego ciągu znaków i zwróć zapisane ciągi.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Pułapki i przypadki brzegowe

Dopuszczanie ), gdy closed < n, zamiast closed < opened. W ten sposób powstaje ())(, które zamyka parę, która nigdy nie została otwarta.
Sprawdzanie tylko tego, czy liczby są równe na końcu. To akceptuje )(; bilans musi wynosić 0 lub więcej na każdym kroku.
Próbowanie ) przed (. Poprawne ciągi pojawiają się w odwrotnej kolejności.
Zapisywanie współdzielonego bufora zamiast jego kopii, gdy listy lub obiekty do budowania ciągów znaków są mutowalne. Każda zapisana odpowiedź pokazuje wtedy ten sam bufor, który backtracking ponownie opróżnia.
Ustalanie rozmiaru tablicy wynikowej na podstawie zbyt optymistycznego szacunku. n = 8 daje 1,430 odpowiedzi.

Najczęstsze pytania3

Jaka jest złożoność czasowa generowania nawiasów?

Algorytm z nawrotami generuje C(n) = (2n)! / ((n+1)! n!) ciągów, czyli liczbę Catalana, która rośnie jak 4^n / (n^1.5 √π). Zbudowanie i skopiowanie każdego z nich zajmuje O(n), więc czas działania wynosi O(4^n / √n). Dodatkowa pamięć wynosi O(n) na bieżący ciąg i stos wywołań, a do tego dochodzi pamięć na wynik.

Ile jest poprawnych ciągów nawiasów dla n par?

n-ta liczba Catalana: 1, 2, 5, 14, 42, 132, 429 i 1,430 dla n od 1 do 8. Każdy poprawnie utworzony ciąg dzieli się na ( A ) B, gdzie to ) pasuje do pierwszego (, a A i B mają po n - 1 parach. Sumowanie względem rozmiaru A daje rekurencję Catalana.

Czy problem generowania nawiasów można rozwiązać bez rekurencji?

Tak. Przechowuj stos częściowych stanów, z których każdy jest ciągiem znaków zawierającym dwa liczniki, i rozszerzaj każdy stan zgodnie z tymi samymi dwiema regułami. Umieść rozszerzenie ) na stosie przed rozszerzeniem (, aby najpierw zdjąć ze stosu to dla (, a wynik pozostał posortowany.

def generateParenthesis(n):
    # Wpisz tutaj kod

Test #1

Test #2

Argument

n = 3

Oczekiwany wynik

["((()))", "(()())", "(())()", "()(())", "()()()"]