Generate all valid parenthesis with three types of parentheses

userMLtM 0
Viewed 28

I encountered the problem of generating all combinations of valid parenthesis in a given length, when there is only one type of parenthesis - ( and ).

The solution I wrote is:

def generate(n, open, close, seq):
    i = open + close
    if i >= 2 * n:
        print(seq)
        return
    if open < n:
        generate(n, open + 1, close, seq + "(")
    if close < open:
        generate(n, open, close + 1, seq + ")")

I am trying to figure out it this can be extended to three different parenthesis, (), [], {}, when expression is valid when it is balanced and contains exactly n parenthesis of each type (and thus, the length of the expression is 6n).

I thought about passing more arguments (n, open1, close1, open2, close2, open3, close3), but the calls cannot keep track of the last open parenthesis. I tried adding another argument which stores the last type, but this allows me only to remember the last type.

Can it be done without using a data structure and only use recursion?

parentheses recursion
1 Answers

It could be optimized but it's the first idea that came to mind. Does this get you started?

def generate(n, open, close):
  if n < 0: return
  if n == 0: yield ""
  for (left, right) in zip(open, close):
    for _ in generate(n - 1, open, close):
      yield left + right + _ # before []...
      yield left + _ + right # around [...]
      yield _ + left + right # after  ...[]

def unique(iterable):
  s = set()
  for x in iterable:
    if not x in s:
      s.add(x)
      yield x

for p in unique(generate(2, "([<", ")]>")):
  print(p)

()()
(())
()[]
([])
[]()
()<>
(<>)
<>()
[()]
[][]
[[]]
[]<>
[<>]
<>[]
<()>
<[]>
<><>
<<>>

for p in unique(generate(3, "([<", ")]>")):
  print(p)

()()()
(()())
()(())
((()))
(())()
()()[]
(()[])
()[]()
()([])
(([]))
([])()
([]())
[]()()
()()<>
(()<>)
()<>()
()(<>)
((<>))
(<>)()
(<>())
<>()()
()[()]
([()])
[()]()
()[][]
([][])
[][]()
()[[]]
([[]])
[[]]()
()[]<>
([]<>)
[]<>()
()[<>]
([<>])
[<>]()
()<>[]
(<>[])
<>[]()
()<()>
(<()>)
<()>()
()<[]>
(<[]>)
<[]>()
()<><>
(<><>)
<><>()
()<<>>
(<<>>)
<<>>()
[()()]
[](())
[(())]
(())[]
[]()[]
[()[]]
[]([])
[([])]
([])[]
[[]()]
[]()<>
[()<>]
[](<>)
[(<>)]
(<>)[]
[<>()]
<>()[]
[][()]
[[()]]
[()][]
[][][]
[[][]]
[][[]]
[[[]]]
[[]][]
[][]<>
[[]<>]
[]<>[]
[][<>]
[[<>]]
[<>][]
[<>[]]
<>[][]
[]<()>
[<()>]
<()>[]
[]<[]>
[<[]>]
<[]>[]
[]<><>
[<><>]
<><>[]
[]<<>>
[<<>>]
<<>>[]
<()()>
<>(())
<(())>
(())<>
<()[]>
<>([])
<([])>
([])<>
<[]()>
<>()<>
<()<>>
<>(<>)
<(<>)>
(<>)<>
<<>()>
<>[()]
<[()]>
[()]<>
<[][]>
<>[[]]
<[[]]>
[[]]<>
<>[]<>
<[]<>>
<>[<>]
<[<>]>
[<>]<>
<<>[]>
<><()>
<<()>>
<()><>
<><[]>
<<[]>>
<[]><>
<><><>
<<><>>
<><<>>
<<<>>>
<<>><>
Mulan0
Related