Wyzwanie Podjęte stąd i również tutaj
N sekwencji nawiasy składa n (
S n )
s.
Prawidłową sekwencję nawiasów definiuje się następująco:
Możesz znaleźć sposób, aby powtórzyć kasowanie sąsiedniej pary nawiasów „()”, aż stanie się pusta.
Na przykład,
(())
jest prawidłowym nawiasami, możesz usunąć parę na 2. i 3. pozycji i staje się ona()
, a następnie możesz ją opróżnić.)()(
nie jest prawidłowym nawiasami, po skasowaniu pary na 2. i 3. pozycji staje się ona)(
i nie można jej już usunąć
Zadanie
Biorąc pod uwagę liczbę n , musisz wygenerować wszystkie prawidłowe sekwencje nawiasów w porządku leksykograficznym
Dane wyjściowe mogą być tablicą, listą lub łańcuchem (w tym przypadku sekwencją na wiersz)
Można użyć innego parę nawias takie jak {}
, []
, ()
lub jakiegokolwiek otwartego blisko znak
Przykład
n = 3
((())) (()()) (())() ()(()) ()()()
n = 2
(()) ()()
źródło
1
s i-1
s)?Odpowiedzi:
Perl 6 , 36 bajtów
Wypróbuj online!
Znajduje wszystkie posortowane leksykograficznie kombinacje2 n
[]
i filtruje te, któreEVAL
poprawnie. Zauważ, że wszystkie prawidłowe kombinacje (nawet podobne[][]
) oceniają na[]
(co jest falsey, ale mynot
(!
), aby odróżnić odtry
zwracaniaNil
)Wyjaśnienie:
źródło
[][]
to kawałek Zen pustej tablicy, która daje tablicę samą w sobie. Plasterek można zastosować wiele razy, więc[][][][]...
ocenia[]
. Poza tym[[]]
nie konstruuje tablicy zagnieżdżonej, ale pustą tablicę z powodu reguły pojedynczego argumentu (musisz napisać[[],]
dla tablicy zagnieżdżonej). Więc każda zrównoważona sekwencja[]
nawiasów powoduje pustą tablicę, która przyjmuje wartość false.R ,
11210799 bajtówPodejście nierekurencyjne. Używamy „<” i „>”, ponieważ pozwala to uniknąć znaków specjalnych w wyrażeniu regularnym. Aby umożliwić nam użycie krótszej specyfikacji dla zakresu ASCII, generujemy ciągi 3 ^ 2n 2n znaków „<”, „=” i „>” przy użyciu
expand.grid
(za pomocą ich kodów ASCII 60, 61 i 62), a następnie grep do zobacz, które kombinacje dają zrównoważone nawiasy otwierające i zamykające. Oczywiście możliwości „=” zostaną zignorowane.Via http://rachbelaid.com/recursive-regular-experession/
Wypróbuj online!
Wyjaśnienie
R , 107 bajtów
Zwykłe podejście rekurencyjne.
-1 dzięki @Giuseppe
Wypróbuj online!
źródło
Map
golfa, ale nie byłem w stanie owinąć wokół niego głowy. Nie jestem przekonany, żeparse
+eval
będzie działać odtąd()()
i tym samym zgłaszać błędy.C (gcc) , 114 bajtów
Wypróbuj online!
Powinien działać dla n <= 15.
Wyjaśnienie
źródło
Python 2 ,
91888481 bajtówWypróbuj online!
-3 bajty dzięki pizzapantom184
źródło
set(...)
zestawem zrozumienia ({...}
) dla -3 bajtów Wypróbuj online!05AB1E , 13 bajtów
Wypróbuj online lub sprawdź więcej przypadków testowych .
Wyjaśnienie:
źródło
Rubinowy , 70 bajtów
Wypróbuj online!
źródło
Japt,
1513 bajtówSpróbuj
Wyjaśnienie
źródło
K (ngn / k) ,
3635 bajtówWypróbuj online!
+!2|&2*x
wszystkie wektory binarne o długości 2 * n(x=+/)#
tylko te, które sumują się do n(&/-1<+\1-2*)#
tylko ci, których sumy częściowe, traktując 0/1 jako 1 / -1, nie są nigdzie ujemne"()"
użyj 0/1 jako indeksów w tym ciąguźródło
Perl 5
-n
,4139 bajtów-2 bajty z nawiasami kątowymi
Wypróbuj online!
Port mojej odpowiedzi na Perla 6.
źródło
Perl 6 , 42 bajtów
Wypróbuj online!
Używa wyrażenia regularnego. Alternatywne podstawienie:
S/[\(<~~>\)]*//
38 bajtów z 0 i 1 jako symbolami otwarcia / zamknięcia:
Wypróbuj online!
Wyjaśnienie
źródło
Retina 0.8.2 , 50 bajtów
Wypróbuj online! Wykorzystuje
<>
s. Wyjaśnienie:Konwertuj na unary.
Podwój wynik.
Wymień wszystkie 2 inary 2n-bitowe liczby binarne, odwzorowując cyfry na
<>
.Zachowaj tylko zrównoważone sekwencje. Wykorzystuje to wyważoną sztuczkę w nawiasach odkrytą przez @MartinEnder.
źródło
JavaScript (ES6),
112102 bajtówJest to w dużej mierze oparte na odpowiedzi C. nwellnhofa .
Wypróbuj online!
źródło
Czerwony ,
214,184136 bajtówWypróbuj online!
Wykorzystuje podejście Jo Kinga. Znajduje wszystkie możliwe układy nawiasów za pomocą rekurencji (są one generowane w porządku leksykograficznym) i drukuje je, jeśli układ oceni jako poprawny blok.
źródło
Galaretka , 19 bajtów
Wypróbuj online!
Dane wyjściowe wyjaśnione w odniesieniu do TIO.
źródło