Строка скобки определяется как строка, состоящая из символов, *()[]в которых скобки соответствуют правильно:

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

Это правильная скобка:

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

Но это не так:

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

Ваша задача - написать программу (или функцию), которая, учитывая положительное целое число n, принимает число в качестве входных данных и выводит (или возвращает) все действительные строки скобок длины n.

Характеристики

• Вы можете выводить строки в любом порядке.
• Вы можете вывести в виде списка или строки, разделенных другим символом.
• Ваша программа должна обрабатывать 0 правильно. Существует 1 возможная скобка длиной 0, которая является пустой строкой "".
• Это код-гольф , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.

Тестовые случаи

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

Желе, 29 байт

-3 байта благодаря @JonathanAllan

Пожалуйста , сообщите мне, если есть какие-либо проблемы / ошибки / ошибки или байты, которые я могу устранить!

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

Попробуйте онлайн!

Предыдущее решение (я) у меня было:

“[(*)]”ṗµḟ”*œṣ⁾()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ị

Объяснение (Моя лучшая попытка описания):

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

Пролог, 69 байт

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

Одним из наиболее интересных свойств Prolog является то, что во многих случаях он способен запускать программу в обратном направлении; например, вместо того, чтобы проверять, является ли что-то истинным, вы можете сгенерировать все решения, для которых оно истинно, и вместо проверки длины строки вы можете сгенерировать все строки с заданной длиной. (Еще одним приятным свойством Prolog является то, что ему требуется пробел после конца каждого определения предиката, и новая строка может быть вставлена ​​так же дешево, как пробел; таким образом, даже программы для игры в гольф часто довольно читабельны.)

Выше определен предикат (эквивалент функции), bкоторый проверяет, имеет ли строка заданную длину и является ли она «фигурной скобкой», как определено в вопросе. В частности, он делает это через поддержку грамматики / регулярного выражения / сопоставления шаблонов Пролога, которая дает хороший, короткий сахар для определения такого рода выражений (очевидно, это стандартное / переносимое приложение, но я не знал об этом, когда первоначально писал ответ, и, таким образом, Предполагается, что ответ будет работать только для одной реализации Пролога, но, похоже, он работает для каждой реализации, которая соответствует стандартам. Программа может быть переведена на английский язык довольно напрямую; первые две строки говорят: «a s - пустая строка, или за e следует a s ; a eявляется звездочкой, или s за которым следует нуль строка «.в скобках или s в квадратных скобках ". Третья строка может быть интерпретирована как" b из N может быть A, если A является списком с длиной N, а A является s

Я позаботился о том, чтобы написать s(и, таким образом b), чтобы они соответствовали каждой «строке скобок» ровно одним способом (что является причиной того, что оба sи eдолжны существовать, а не группировать их в один предикат). Это делает их обоих полностью обратимыми; таким образом, bможет использоваться для генерации всех «строк скобок» заданной длины, в дополнение к проверке, является ли строка строкой скобок заданной длины (ее также можно использовать в качестве третьего способа округления, чтобы выяснить длину скобки строка, но это почти наверняка ее наименее полезный режим работы). Реализация является рекурсивной, например, чтобы сгенерировать s , код сгенерирует все возможные e , которые не длиннее требуемой длины вывода, и добавит все возможные sкоторые вписываются в оставшееся им пространство; поскольку я заранее указал длину аргумента (в пределах b ), механизм Пролога знает, что он не может генерировать выходные данные, длина которых превышает заданную длину, что позволяет завершить рекурсию.

Вот пример работающей программы:

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

Haskell, 101 94 байта

7 байт сохранено 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<-["()","[]"]]

Практически просто, следуя определению, но с ""делом перенесено.

Использование:

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

(Второе вычисление занимает менее секунды на медленной машине.)

Я также хотел бы поделиться результатом другого подхода, который я предложил, думая о генерации функций. Он определяет список b списков строк, который b!!nсодержит все строки скобок длины n. Точно так же u!!nсодержит все атомы размера n-1. Приятно то, что в коде не используются никакие числа. Это не полностью игра в гольф: uи iможет быть встроено, и это, безусловно, упускает несколько других возможностей для игры в гольф. К сожалению, не похоже, что его можно сделать короче, чем в первой версии, но он вычисляется length $ b !! 10еще быстрее.

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 байт

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

объяснение

Characters@"*([)]"

Найдите символы строки "*([)]", дающие List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Найдите кортежи из приведенного выше списка с длиной n.

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

Безымянная логическая функция, чтобы определить, сбалансирован ли кортеж:

#/."*"->Nothing

Удалить все "*"на входе.

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

Повторно удаляйте все последовательные вхождения "("и ")"или "["и "]"до тех пор, пока ввод не изменится.

... =={}

Проверьте, является ли результат пустым List.

Select[ ... , ... ]

Найдите кортежи, которые дают, Trueкогда применяется булева функция.

#<>""&/@

Преобразуйте каждого Listиз символов в Strings.

Python 2, 128 байт

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

Винт рекурсивных регулярных выражений - мы используем парсер Python! Чтобы убедиться, что, например, *(**[])*это строка-скобка, мы делаем следующее:

1. Создайте строку наподобие "*", (0,"*","*", [0,0] ,0) ,"*", где каждый второй символ из четырех является символом из скобок, а остальные символы являются клеем, чтобы сделать это потенциальным выражением Python.

2. eval Это.

3. Если это не приводит к ошибке, выведите s[1::4](символы скобок).

В клеевых символах выбраны так , что строка я делаю это правильное выражение Python , если и только если принимать каждый второй символ из четырех выходов действительной скобки-струнных.

PHP, 149 байт

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));

Использует старый добрый генерировать все возможные, а затем метод фильтрации. Используйте как:

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 байта

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

repl.it

Безымянная функция, которая возвращает список допустимых строк длины n.
Формы всех длины nкортежи персонажей *()[], соединяют их в строки , используя map(''.join,...)и фильтры для тех , которые имеют сбалансированные скобки, удаляя «пар» "*", "()"и , "[]"в свою очередь , nи проверьте , что результат является пустой строкой ( nраз это перебор, особенно для "*"но гольфист).

Сетчатка , 78 байт

Количество байтов предполагает кодировку ISO 8859-1.

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

A`;

Попробуйте онлайн!

объяснение

Я генерирую все возможные строки длиной 5, а затем отфильтровываю неверные.

.+
$*

Это преобразует ввод в унарный, используя 1в качестве цифры.

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

Это многократно ( +) заменяет первый ( 1) по одному в каждой строке ( %) таким образом, что он делает пять копий строки, по одной для каждого возможного символа. Это делается с помощью замены префикса и суффикса, $`и$' для создания остатка каждой строки.

Этот цикл останавливается, когда нет больше 1 для замены. На данный момент у нас есть все возможные строки длины N, по одной на каждой строке.

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

Эти два этапа выполняются для каждой строки отдельно ( %). На первом этапе просто дублируется строка с ;разделением двух копий.

Второй этап является еще цикл ( +), который удаляет повторно [], ()или *от первой копии строки, или удаляет точку с запятой в начале строки (что возможно только после того, как строка исчезла полностью).

A`;

Допустимые строки - это те, у которых больше нет точки с запятой, поэтому мы просто отбрасываем все строки ( A), которые содержат точку с запятой.

Python 3.5, 146 байт

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

Очень длинный по сравнению с другими ответами, но самый короткий, который я смог найти. Она имеет форму анонимной лямбда-функции и поэтому должна вызываться в формате

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

Выходы в Python набор из неупорядоченных строк , представляющих все возможные фигурных скобки-строки длины входного сигнала.

Например, предполагая, что названная выше функция названа G, вызов G(3)приведет к следующему выводу:

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

Попробуйте онлайн! (Ideone)

Однако, если, как и я, вы на самом деле не являетесь поклонником упрощения вещей с помощью встроенных модулей, то вот мой собственный оригинальный ответ - не использовать какие-либо внешние библиотеки для поиска перестановок, и в настоящее время он занимает колоссальные 288 237 байт :

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)]

Опять же, как и в случае с конкурирующим ответом, этот ответ имеет форму лямбда-функции и поэтому должен также вызываться в формате

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

И выводит Python список из неупорядоченных строк , представляющих все фигурные скобки-строку длины входа. Например, если лямбда должна быть вызвана как G(3), на этот раз результат будет следующим:

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

Кроме того, этот также намного быстрее, чем мой другой ответ, он может найти все скобки длиной 11около 115 секунд , длиной 10около 19 секунд , длиной 9около 4 секунд и длиной 8в около 0,73 секунды на моей машине, тогда как мой конкурирующий ответ занимает намного больше времени, чем 115 секунд для ввода 6.

Попробуйте онлайн! (Ideone)

05AB1E, 23 байта

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

Некоторые из этих функций могли быть реализованы после публикации вопроса. Любые предложения приветствуются!

Попробуйте онлайн!

Как?

…[(* - 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