Generate all Brain-Flak Snippets

Question

This question is the second of several Brain-flak Birthday challenges designed to celebrate Brain-Flak's first Birthday! You can find more information about Brain-Flak's Birthday here

Challenge

For this challenge you'll be generating all fully matched strings from a list of brackets. To borrow DJMcMayhem's definition of a fully matched string:

• For the purpose of this challenge, a "bracket" is any of these characters: ()[]{}<>.

• A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

  ()
  []{}
  

  Or if every subelement inside of it is also matched.

  [()()()()]
  {<[]>}
  (()())
  

  Subelements can also be nested several layers deep.

  [(){<><>[()]}<>()]
  <[{((()))}]>
  

• A string is considered "Fully matched" if and only if each pair of brackets has the correct opening and closing bracket in the right order.

---

Input

Your program or function will take a list of four non-negative numbers in any convenient, consistent format. This includes (but is not limited to) a list of integers, a non-digit delimited string, or separate arguments. These four numbers represent the number of matched pairs of each type of bracket. For example, [1,2,3,4] would represent:

• 1 pair of ()

• 2 pairs of {}

• 3 pairs of [] and

• 4 pairs of <>

You may choose which pair of brackets each input corresponds to as long as it is consistent.

Output

You should output all fully matched string that can be formed from this list of brackets without duplicates. Output can be in any reasonable format which includes printing a non-bracket delimited string to STDOUT, or a list of strings as a return value from a function.

Your algorithm must work for any arbitrary input, but you don't need to worry about memory, time or integer size limits (e.g. if your answer is in C you won't get 2³³ as an input).

This is code-golf, so the shortest answer in bytes wins.

Example Input and Output

For these example I will use the same input order as above.

For each example, the first line will be input and the following lines will be the output

Example 0:
[0,0,0,0]


Example 1:
[1,0,0,0]
()

Example 2:
[0,2,0,0]
{}{}
{{}}

Example 3:
[0,0,1,1]
[]<>
[<>]
<[]>
<>[]

Example 4:
[0,1,2,0]
{}[][]  {}[[]]  {[]}[]  {[][]}  {[[]]} 
[{}][]  [{}[]]  [{[]}]  []{}[]  []{[]} 
[][{}]  [][]{}  [[{}]]  [[]{}]  [[]]{}

Example 5:
[1,0,0,3]
()<><><>  ()<><<>>  ()<<>><>  ()<<><>>  ()<<<>>>  (<>)<><>  (<>)<<>>
(<><>)<>  (<><><>)  (<><<>>)  (<<>>)<>  (<<>><>)  (<<><>>)  (<<<>>>)
<()><><>  <()><<>>  <()<>><>  <()<><>>  <()<<>>>  <(<>)><>  <(<>)<>>
<(<><>)>  <(<<>>)>  <>()<><>  <>()<<>>  <>(<>)<>  <>(<><>)  <>(<<>>)
<><()><>  <><()<>>  <><(<>)>  <><>()<>  <><>(<>)  <><><()>  <><><>()
<><<()>>  <><<>()>  <><<>>()  <<()>><>  <<()><>>  <<()<>>>  <<(<>)>>
<<>()><>  <<>()<>>  <<>(<>)>  <<>>()<>  <<>>(<>)  <<>><()>  <<>><>()
<<><()>>  <<><>()>  <<><>>()  <<<()>>>  <<<>()>>  <<<>>()>  <<<>>>()

Example 6:
[1,1,1,1]

(){}[]<>  (){}[<>]  (){}<[]>  (){}<>[]  (){[]}<>  (){[]<>}  (){[<>]}
(){<[]>}  (){<>}[]  (){<>[]}  ()[{}]<>  ()[{}<>]  ()[{<>}]  ()[]{}<>
()[]{<>}  ()[]<{}>  ()[]<>{}  ()[<{}>]  ()[<>{}]  ()[<>]{}  ()<{}[]>
()<{}>[]  ()<{[]}>  ()<[{}]>  ()<[]{}>  ()<[]>{}  ()<>{}[]  ()<>{[]}
()<>[{}]  ()<>[]{}  ({})[]<>  ({})[<>]  ({})<[]>  ({})<>[]  ({}[])<>
({}[]<>)  ({}[<>])  ({}<[]>)  ({}<>)[]  ({}<>[])  ({[]})<>  ({[]}<>)
({[]<>})  ({[<>]})  ({<[]>})  ({<>})[]  ({<>}[])  ({<>[]})  ([{}])<>
([{}]<>)  ([{}<>])  ([{<>}])  ([]){}<>  ([]){<>}  ([])<{}>  ([])<>{}
([]{})<>  ([]{}<>)  ([]{<>})  ([]<{}>)  ([]<>){}  ([]<>{})  ([<{}>])
([<>{}])  ([<>]){}  ([<>]{})  (<{}[]>)  (<{}>)[]  (<{}>[])  (<{[]}>)
(<[{}]>)  (<[]{}>)  (<[]>){}  (<[]>{})  (<>){}[]  (<>){[]}  (<>)[{}]
(<>)[]{}  (<>{})[]  (<>{}[])  (<>{[]})  (<>[{}])  (<>[]){}  (<>[]{})
{()}[]<>  {()}[<>]  {()}<[]>  {()}<>[]  {()[]}<>  {()[]<>}  {()[<>]}
{()<[]>}  {()<>}[]  {()<>[]}  {([])}<>  {([])<>}  {([]<>)}  {([<>])}
{(<[]>)}  {(<>)}[]  {(<>)[]}  {(<>[])}  {}()[]<>  {}()[<>]  {}()<[]>
{}()<>[]  {}([])<>  {}([]<>)  {}([<>])  {}(<[]>)  {}(<>)[]  {}(<>[])
{}[()]<>  {}[()<>]  {}[(<>)]  {}[]()<>  {}[](<>)  {}[]<()>  {}[]<>()
{}[<()>]  {}[<>()]  {}[<>]()  {}<()[]>  {}<()>[]  {}<([])>  {}<[()]>
{}<[]()>  {}<[]>()  {}<>()[]  {}<>([])  {}<>[()]  {}<>[]()  {[()]}<>
{[()]<>}  {[()<>]}  {[(<>)]}  {[]()}<>  {[]()<>}  {[](<>)}  {[]}()<>
{[]}(<>)  {[]}<()>  {[]}<>()  {[]<()>}  {[]<>()}  {[]<>}()  {[<()>]}
{[<>()]}  {[<>]()}  {[<>]}()  {<()[]>}  {<()>}[]  {<()>[]}  {<([])>}
{<[()]>}  {<[]()>}  {<[]>()}  {<[]>}()  {<>()}[]  {<>()[]}  {<>([])}
{<>}()[]  {<>}([])  {<>}[()]  {<>}[]()  {<>[()]}  {<>[]()}  {<>[]}()
[(){}]<>  [(){}<>]  [(){<>}]  [()]{}<>  [()]{<>}  [()]<{}>  [()]<>{}
[()<{}>]  [()<>{}]  [()<>]{}  [({})]<>  [({})<>]  [({}<>)]  [({<>})]
[(<{}>)]  [(<>){}]  [(<>)]{}  [(<>{})]  [{()}]<>  [{()}<>]  [{()<>}]
[{(<>)}]  [{}()]<>  [{}()<>]  [{}(<>)]  [{}]()<>  [{}](<>)  [{}]<()>
[{}]<>()  [{}<()>]  [{}<>()]  [{}<>]()  [{<()>}]  [{<>()}]  [{<>}()]
[{<>}]()  [](){}<>  [](){<>}  []()<{}>  []()<>{}  []({})<>  []({}<>)
[]({<>})  [](<{}>)  [](<>){}  [](<>{})  []{()}<>  []{()<>}  []{(<>)}
[]{}()<>  []{}(<>)  []{}<()>  []{}<>()  []{<()>}  []{<>()}  []{<>}()
[]<(){}>  []<()>{}  []<({})>  []<{()}>  []<{}()>  []<{}>()  []<>(){}
[]<>({})  []<>{()}  []<>{}()  [<(){}>]  [<()>{}]  [<()>]{}  [<({})>]
[<{()}>]  [<{}()>]  [<{}>()]  [<{}>]()  [<>(){}]  [<>()]{}  [<>({})]
[<>{()}]  [<>{}()]  [<>{}]()  [<>](){}  [<>]({})  [<>]{()}  [<>]{}()
<(){}[]>  <(){}>[]  <(){[]}>  <()[{}]>  <()[]{}>  <()[]>{}  <()>{}[]
<()>{[]}  <()>[{}]  <()>[]{}  <({})[]>  <({})>[]  <({}[])>  <({[]})>
<([{}])>  <([]){}>  <([])>{}  <([]{})>  <{()}[]>  <{()}>[]  <{()[]}>
<{([])}>  <{}()[]>  <{}()>[]  <{}([])>  <{}[()]>  <{}[]()>  <{}[]>()
<{}>()[]  <{}>([])  <{}>[()]  <{}>[]()  <{[()]}>  <{[]()}>  <{[]}()>
<{[]}>()  <[(){}]>  <[()]{}>  <[()]>{}  <[({})]>  <[{()}]>  <[{}()]>
<[{}]()>  <[{}]>()  <[](){}>  <[]()>{}  <[]({})>  <[]{()}>  <[]{}()>
<[]{}>()  <[]>(){}  <[]>({})  <[]>{()}  <[]>{}()  <>(){}[]  <>(){[]}
<>()[{}]  <>()[]{}  <>({})[]  <>({}[])  <>({[]})  <>([{}])  <>([]){}
<>([]{})  <>{()}[]  <>{()[]}  <>{([])}  <>{}()[]  <>{}([])  <>{}[()]
<>{}[]()  <>{[()]}  <>{[]()}  <>{[]}()  <>[(){}]  <>[()]{}  <>[({})]
<>[{()}]  <>[{}()]  <>[{}]()  <>[](){}  <>[]({})  <>[]{()}  <>[]{}()

Answer 1

Haskell, 128 bytes

f is the main function, it takes a list of Ints and returns a list of Strings.

f=g.($zip"({[<"")}]>").zipWith replicate
g=max[""].(#g)
l#c=[b:s|x@(b,e):r<-l,s<-(r:filter(/=x:r)l)?(map(e:).c)]
l?c=c l++l#(?c)

Try it online!

How it works

• f transforms its input list into a list of lists of tuples, each tuple containing a bracket pair, with each type of bracket in its own sublist. E.g. [1,2,0,0] becomes [[('{','}')],[('[',']'),('[',']')]]. Then it calls g with the transformed list.
• The remaining functions use a partially continuation-passing style intermingled with list manipulation. Each continuation function c takes a list l of remaining bracket tuple lists and returns a list of possible strings to be suffixed to what's already been generated.
• g l generates the list of fully matched strings formable by using all the brackets in l.
  • It does this by calling l#g to generate strings beginning with some bracket. The recursive g parameter is itself used as a continuation by #, to generate what comes after the first bracketed subelement.
  • In the case where there are no such strings (because l has no brackets left inside) g instead returns [""], the list containing just the empty string. Since [""] compares smaller to all nonempty lists produceable by #, we can do this by applying max.
• l#c generates strings from l beginning with at least one bracketed subelement, leaving to the continuation c to determine what follows the element.
  • b and e are a selected pair of brackets in the tuple x, and r is the list of remaining tuples of the same bracket type.
  • r:filter(/=x:r)l is l with the tuple x removed, slightly rearranged.
  • ? is called to generate the possible subelements between b and e. It gets its own continuation map(e:).c, which prefixes e to each of the suffix strings generated by c.
  • # itself prepends the initial b to all the strings generated by ? and c.
• l?c generates the fully matched strings formable by using zero or more bracket pairs from l, and then leaves to its continuation c to handle what's left over. The c l part goes directly to c without adding any subelements, while l#(?c) uses # to generate one subelement and then call (?c) recursively for possible further ones.

Answer 2

Jelly, 50 40 34 bytes

-6 bytes thanks to Leaky Nun (getting reduce to work where I couldn't)

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ

Plain and inefficient.

Try it online! (times out at TIO for [1,1,1,1] - yes, inefficient.)

How?

Recursively removes pairs of matching brackets that reside right next to each other until no more may be removed for every possible string one may form, keeping such strings which reduce to nothing (hence have all matching content).

“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ - Main link: list: [n(), n{}, n[], n<>]
“()“{}“[]“<>”                      - literal ["()", "{}", "[]", "<>"]
             ©                     - copy to register
               "                   - zip with:
              ẋ                    -   repeat list
                F                  - flatten
                 Œ!                - all permutations (yeah, it's inefficient!)
                   Q               - de-duplicate
                    µ              - monadic chain separation
                                Ðḟ - filter discard if (non empty is truthy):
                             µÐL   -   loop until no change:
                       ®           -     recall value from register
                     W             -     wrap loop variable in a list
                      ;            -     concatenate
                           ¥/      -     reduce with last two links as a dyad:
                        œṣ         -       split left on occurrences of sublist on the right
                          F        -       flatten the result

Answer 3

05AB1E, 33 32 30 27 25 bytes

Saved 7 bytes thanks to Riley.

Input order is [(),<>,[],{}]

žu4äשJœJÙD[D®õ:DŠQ#]€g_Ï

Try it online!

Explanation

žu                             # push the string "()<>[]{}"
  4ä                           # split in 4 parts
    ©                          # store a copy in register
     ×                         # repeat each bracket a number of times decided by input
      JœJÙ                     # get the unique permutations of the string of brackets
          D                    # duplicate
           [                   # start infinite loop
            D                  # duplicate current list of permutations
             ®õ:               # replace any instance of (), [], <>, {} 
                               # with an empty string
                DŠ             # duplicate and move down 2 places on stack
                  Q#           # if the operation didn't alter the list, exit loop
                    ]          # end loop
                     €g        # get the length of each subtring
                       _Ï      # keep only the strings in the original 
                               # list of unique permutations 
                               # that have a length of 0 in the resulting list

Answer 4

Pyth - 83 74 71 63 bytes

K("\[]""{}""\(\)""<>")Fd{.psm*:@Kd*\\2k@QdU4JdVldFHK=:JHk))I!Jd

Try It

1: Kc"[] {} () <>")Fd{.ps*V-R\KQJdVldFHK=:JHk))I!Jd

Also, this 53-byte version thanks to Leaky Nun

Kc"\[] \{} \(\) <>")Fd{.ps*V-R\\KQJdVldFHK=:JHk))I!Jd

Here

Answer 5

Ruby, 123 bytes

->a{"<>{}[]()".gsub(/../){$&*a.pop}.chars.permutation.map(&:join).uniq.grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}

Try it online! It's inefficient, though, so even inputs like [1,2,1,1] will time out online. All the listed examples will work, at least!

Explanation

->a{                                        # Procedure with input a
    "<>{}[]()".gsub(/../){                  # For all pairs of brackets
                          $&*a.pop          # Pop last item in input, then repeat
                                            #   the bracket pair by that number
                                  }.chars   # Get characters
        .permutation                        # All permutations of characters
                    .map(&:join)            # For each permutation, join the chars
                                .uniq       # Get unique permutations only
            .grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}
                                            # Only return permutations that match
                                            #   this bracket-matching regex