Ciąg nawiasów klamrowych jest zdefiniowany jako ciąg składający się ze znaków, *()[]w których nawiasy klamrowe pasują poprawnie:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

To jest prawidłowy nawias klamrowy:

((())***[]**)****[(())*]*

Ale to nie są:

)(
**(**[*](**)
**([*)]**

Twoim zadaniem jest napisanie programu (lub funkcji), który przy dodatniej liczbie całkowitej nprzyjmuje liczbę jako dane wejściowe i wyjściowe (lub zwraca) wszystkie prawidłowe ciągi nawiasów o długości n.

Dane techniczne

• Możesz wyprowadzać ciągi w dowolnej kolejności.
• Możesz generować jako listę lub ciąg znaków oddzielony innym znakiem.
• Twój program musi poprawnie obsługiwać 0. Istnieje 1 możliwy ciąg nawiasu klamrowego o długości 0, który jest pustym ciągiem "".
• To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*

Galaretka, 29 bajtów

-3 bajty dzięki @JonathanAllan

Proszę powiadom mnie, jeśli są jakieś problemy / bugi / błędy lub bajty mogę strącać!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Wypróbuj online!

Poprzednie rozwiązania miałem:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Objaśnienie (Moja najlepsza próba opisu):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter

Prolog, 69 bajtów

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

Jedną z najbardziej interesujących właściwości Prologa jest to, że w wielu przypadkach jest on w stanie uruchomić program wstecz; na przykład, zamiast sprawdzać, czy coś jest prawdą, możesz wygenerować wszystkie rozwiązania, dla których jest to prawda, i zamiast sprawdzać długość łańcucha, możesz wygenerować wszystkie łańcuchy o określonej długości. (Inną fajną właściwością Prologa jest to, że wymaga on spacji po zakończeniu każdej definicji predykatu, a nową linię można wstawić tak tanio jak spację; w ten sposób nawet programy w golfa są często dość czytelne).

Powyższe definiuje predykat (odpowiednik funkcji), bktóry sprawdza, czy łańcuch ma określoną długość i jest „łańcuchem nawiasowym”, jak zdefiniowano w pytaniu. Dokładniej, robi to poprzez wsparcie gramatyki Prologa / wyrażenia regularnego / dopasowania wzorca, które daje trochę miłego, krótkiego cukru do zdefiniowania tego rodzaju wyrażeń (najwyraźniej jest to standardowy / przenośny, ale nie wiedziałem o tym podczas pisania odpowiedzi, a zatem założono, że odpowiedź zadziała tylko na jednej implementacji Prolog; wydaje się, że działa na każdej implementacji zgodnej ze standardami). Program można bezpośrednio przetłumaczyć na angielski; pierwsze dwa wiersze mówią: „ s jest pustym ciągiem lub e po którym następuje s ; an ejest gwiazdką lubsw nawiasach lub sw nawiasach kwadratowych. Trzeci wiersz może być interpretowany jako „ b z N może być A, jeśli A jest listą o długości N, a A to s, po którym następuje łańcuch zerowy”.

Wziąłem trochę opieki napisać s(i tym samym b), tak aby dopasować każdy nawias „ciąg” w dokładnie jeden sposób (co jest powodem, że zarówno si emuszą istnieć, zamiast grupując je w jednym orzecznika). To sprawia, że ​​oba są całkowicie odwracalne; dlatego bmożna go wykorzystać do wygenerowania wszystkich „łańcuchów nawiasu klamrowego” o danej długości, oprócz testowania, czy łańcuch jest struną nawiasu klamrowego o danej długości (można go również użyć w drugą stronę, aby obliczyć długość nawiasu string, ale prawie na pewno jest to najmniej przydatny tryb działania). Implementacja jest rekurencyjna, np. Aby wygenerować s , kod wygeneruje wszystkie możliwe e , które nie są dłuższe niż wymagana długość wyjścia, i dołączy wszystkie możliwe ss, które pasują do nich w pozostałej przestrzeni; ponieważ z góry podałem długość argumentu (w ramach b ), silnik Prolog wie, że nie może wygenerować wyniku dłuższego niż podana długość, co pozwala na zakończenie rekursji.

Oto przykład działającego programu:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

Haskell, 101 94 bajtów

7 bajtów zapisanych przez Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Prawie proste, zgodne z definicją, ale z ""przeniesioną obudową.

Posługiwać się:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(Drugie obliczenie zajmuje mniej niż sekundę na wolnym komputerze).

Chciałbym również podzielić się wynikiem innego podejścia, które wymyśliłem, myśląc o generowaniu funkcji. Definiuje listę b takich łańcuchów, która b!!nzawiera wszystkie łańcuchy nawiasów o długości n. Podobnie u!!nzawiera wszystkie atomy wielkości n-1. Jedną fajną rzeczą jest to, że kod nie używa żadnych cyfr. To nie jest całkowicie golfed: ui imogą być wstawiane, a to z pewnością nie zdobywa kilka innych możliwości gry w golfa. Niestety nie wygląda na to, że można go skrócić do pierwszej wersji, ale oblicza się length $ b !! 10jeszcze szybciej.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)

Mathematica, 116 bajtów

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Wyjaśnienie

Characters@"*([)]"

Znajdź znaki ciągu "*([)]", podając List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Znajdź krotki z powyższej listy o długości n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Nienazwana funkcja boolowska, aby sprawdzić, czy krotka jest zrównoważona:

#/."*"->Nothing

Usuń wszystko "*"z wejścia.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Wielokrotnie usuwaj wszystkie kolejne wystąpienia "("i ")"lub "["i "]"dopóki dane wejściowe się nie zmienią.

... =={}

Sprawdź, czy wynik jest pusty List.

Select[ ... , ... ]

Znajdź krotki, które dają Truepo zastosowaniu funkcji boolowskiej.

#<>""&/@

Konwertuj każdy Listze znaków na Strings.

Python 2, 128 bajtów

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Przykręć rekursywne wyrażenia regularne - używamy parsera Pythona! Aby sprawdzić, na przykład, że *(**[])*jest to nawias klamrowy, wykonujemy następujące czynności:

1. Utwórz ciąg podobny do tego "*", (0,"*","*", [0,0] ,0) ,"*", w którym co drugi czteroosobowy znak jest znakiem z nawiasów klamrowych, a pozostałe znaki są klejem, aby uczynić z niego potencjalne wyrażenie w języku Python.

2. eval to.

3. Jeśli nie spowoduje to błędu, wydrukuj s[1::4](znaki nawiasu klamrowego).

Do kleju znaki są zbierane tak, że ciąg robię jest poprawnym wyrażeniem Pythona tylko wtedy, gdy przy każdym drugi znak z czterech rentowności ważny klamra-strunowych.

PHP, 149 bajtów

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Używa starego dobrego generowania wszystkich możliwych, a następnie metody filtrowania. Użyj jak:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4

Python, 134 bajty

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Nienazwana funkcja, która zwraca listę prawidłowych ciągów długości n.
Formy wszystkie długość nkrotki bohaterów *()[], łączy je w ciągi korzystających map(''.join,...)i filtry do tych, które zostały zrównoważone nawiasy usuwając „parę” "*", "()"oraz "[]"z kolei nrazy i upewnieniu się, że wynik jest pustym ciągiem znaków ( nczas jest przesadą, zwłaszcza "*"jednak jest golfistą).

Siatkówka , 78 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

Wypróbuj online!

Wyjaśnienie

Generuję wszystkie możliwe ciągi o długości 5, a następnie odfiltrowuję niepoprawne.

.+
$*

Konwertuje to wejście na jednoargumentowe, używając 1jako cyfry.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

To wielokrotnie ( +) zastępuje pierwszy ( 1) jeden w każdej linii ( %) w taki sposób, że tworzy pięć kopii linii, po jednej dla każdego możliwego znaku. Odbywa się to za pomocą podstawień prefiksów i sufiksów $`oraz $'konstruowania reszty każdej linii.

Ta pętla zatrzymuje się, gdy nie ma już 1 do zastąpienia. W tym momencie mamy wszystkie możliwe ciągi długości N, po jednym w każdej linii.

%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

Te dwa etapy są wykonywane osobno dla każdej linii ( %). Pierwszy etap po prostu powiela linię za pomocą; oddziela dwie kopie.

Drugi etap jest inny układ ( +), które wielokrotnie usuwa [], ()lub *z pierwszego kopię łańcucha, lub usuwa średnik na początku linii (co jest możliwe dopiero wtedy, gdy łańcuch jest całkowicie zniknął).

A`;

Prawidłowe ciągi to te, które nie mają już średnika przed nimi, więc po prostu odrzucamy wszystkie linie ( A) zawierające średnik.

Python 3.5, 146 bajtów

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

Bardzo długi w porównaniu z innymi odpowiedziami, ale najkrótszy, jaki udało mi się obecnie znaleźć. Ma on postać anonimowej funkcji lambda i dlatego musi być wywoływany w formacie

print(<Function Name>(<Integer>))

Wyjścia pytona zestawie z nieuporządkowanych ciągów reprezentujących wszystkie możliwe Brace-ciągi długości wejściowego.

Na przykład przy założeniu, że powyższa funkcja ma nazwę G, wywołanie G(3)spowoduje następujące wyniki:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

Wypróbuj online! (Ideone)

Jeśli jednak, podobnie jak ja, nie jesteś fanem upraszczania rzeczy za pomocą wbudowanych funkcji, oto moja własna oryginalna odpowiedź, która nie korzysta z żadnych zewnętrznych bibliotek w celu znalezienia permutacji, a obecnie stoi na ogromnym poziomie 288 237 bajtów :

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

Ponownie, podobnie jak odpowiedź konkurencyjna, ta ma postać funkcji lambda i dlatego należy ją również wywołać w formacie

print(<Function Name>(<Integer>))

Python i wysyła listy z nieposortowane ciągów reprezentujących wszystkie Brace-ciągi długości wejściowego. Na przykład, jeśli lambda G(3)miałaby zostać wywołana jako , tym razem wynik byłby następujący:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Również ten jest również o wiele szybszy niż moja inna odpowiedź, będąc w stanie znaleźć wszystkie nawiasy klamrowe o długości 11w około 115 sekund , te o długości 10w około 19 sekund , o długości 9w około 4 sekundy i te o długości 8w około 0,73 sekundy na moim komputerze, podczas gdy moja konkurencyjna odpowiedź trwa znacznie dłużej niż 115 sekund na wprowadzenie 6.

Wypróbuj online! (Ideone)

05AB1E, 23 bajty

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Niektóre z tych funkcji mogły zostać zaimplementowane po opublikowaniu pytania. Wszelkie sugestie są mile widziane!

Wypróbuj online!

W jaki sposób?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string