# Parentheses sequences in lexicographical order

Challenge Taken from here and also here

An n parentheses sequence consists of n (s and n )s.

A valid parentheses sequence is defined as the following:

You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.

For example, (()) is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes (), then you can make it empty. )()( is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes )( and you cannot erase any more

Given a number n you need to generate all correct parenthesis sequence in lexicographical order

Output can be an array, list or string (in this case a sequence per line)

You can use a different pair of parenthesis such as {}, [], () or any open-close sign

Example

• n = 3

((()))
(()())
(())()
()(())
()()()

• n = 2

(())
()()

• @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge. Nov 6, 2018 at 14:12
• Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6, 2018 at 14:13
• Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge) Nov 6, 2018 at 14:23
• Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets) Nov 6, 2018 at 14:24
• Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like 1s and -1s)? Nov 6, 2018 at 19:51

# Perl 6, 36 bytes

{grep {try !.EVAL},[X~] <[ ]>xx$_*2}  Try it online! Finds all lexographically sorted combinations of $$\2n\$$ []s and filters the ones that EVAL correctly. Note that all valid combinations (even stuff like [][]) evaluate to [] (which is falsey, but we not it (!) to distinguish from try returning Nil) ### Explanation: { } # Anonymous code block <[ ]> # Create a list of ("[", "]") xx$_*2   # Duplicate this 2n times
[X~]               # Find all possible combinations
grep {          },                   # Filter from these
.EVAL                     # The EVAL'd strings
try !                          # That do not throw an error

• If anyone's curious, [][] is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so [][][][]... evaluates to []. Besides, [[]] doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write [[],] for a nested array). So any balanced sequence of [] brackets results in an empty array which boolifies to false. Nov 7, 2018 at 10:48

# R, 112107 99 bytes

Non-recursive approach. We use "<" and ">" because it avoids escape characters in the regex. To allow us to use a shorter specification for an ASCII range, we generate 3^2n 2n-character strings of "<", "=" and ">" using expand.grid (via their ASCII codes 60, 61 and 62) and then grep to see which combinations give balanced open and close brackets. The "=" possibilities will get ignored, of course.

function(n)sort(grep("^(<(?1)*>)(?1)*$",apply(expand.grid(rep(list(60:62),2*n)),1,intToUtf8),,T,T))  Try it online! ## Explanation "^(<(?1)*>)(?1)*$" = regex for balanced <> with no other characters
^ # match a start of the string
( # start of expression 1
< # open <>
(?1)* # optional repeat of any number of expression 1 (recursive)
# allows match for parentheses like (()()())(()) where ?1 is (\$$(?1)*\$$)
> # close <>
) # end of expression 1
(?1)* # optional repeat of any number of expression 1
$# end of string function(n) sort( grep("^(<(?1)*>)(?1)*$", # search for regular expression matching open and close brackets
apply(
expand.grid(rep(list(60:62),2*n)) # generate 3^(2n) 60,61,62 combinations
,1,intToUtf8) # turn into all 3^(2n) combinations of "<","=",">"
,,T,T) # return the values that match the regex, so "=" gets ignored
) # sort them


# R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)if(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))


Try it online!

• ah, I was trying to find a Map golf but couldn't wrap my head around it. I'm not convinced parse + eval is going to work since ()() and the like throw errors. Nov 7, 2018 at 20:03

# K (ngn/k), 36 35 37 bytes

{"()"(|/'0>+\'1-2*)_(x=+/')#+!2|&2*x}


Try it online!

+!2|&2*x all binary vectors of length 2*n

(x=+/')# only those that sum to n

(|/0>+\'1-2*)_ only those whose partial sums, treating 0/1 as 1/-1, are nowhere negative

"()" use 0/1 as indices in this string

# 05AB1E, 13 bytes

„()©s·ãʒ®õ:õQ


Explanation:

„()            # Push string "()"
©           # Store it in the register without popping
s·         # Swap to get the (implicit) input, and double it
ã        # Cartesian product that many times
ʒ       # Filter it by:
®      #  Push the "()" from the register
õ:    #  Infinite replacement with an empty string
õQ  #  And only keep those which are empty after the infinite replacement


# C (gcc), 114 bytes

f(n,x,s,a,i){char b={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}


Try it online!

Should work for n <= 15.

### Explanation

f(n,x,s,a,i){
char b={};   // Output buffer initialized with zeros.
n*=2;            // Double n.
for(x=1<<n;x--;  // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b))  // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;)  // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|=              // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+=            // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1   // Isolate current bit and inc i.
41-(        )  // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]=               // Store ASCII code in buffer.
2*(                    )-81;  // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}


# Python 2, 918884 81 bytes

f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']


Try it online!

-3 bytes thanks to pizzapants184

• Also works in Python 3, I think Nov 7, 2018 at 0:02
• You can replace set(...) with a set comprehension ({...}) for -3 bytes Try it online! Nov 7, 2018 at 15:45

# Ruby, 70 bytes

f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|[]}


Try it online!

# Japt, 15 13 bytes

ç>i<)á Ôke/<>


Try it

## Explanation

ç                 :Input times repeat the following string
>i<              :  ">" prepended with "<"
)             :End repeat
á            :Get unique permutations
Ô          :Reverse
k         :Remove any that return true (non-empty string)
e/<>     :  Recursively replace Regex /<>/


# Perl 5-n, 41 39 bytes

-2 bytes with angle brackets

s/<(?R)*>//gr||say for glob'{<,>}'x2x$_  Try it online! Port of my Perl 6 answer. # Perl 6, 42 bytes {grep {!S:g/$$<~~>*$$//},[X~] <( )>xx$_*2}


Try it online!

Uses a recursive regex. Alternative substitution: S/[$$<~~>$$]*//

38 bytes with 0 and 1 as open/close symbols:

{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}  Try it online! ### Explanation { } # Anonymous block <( )> # List "(", ")" xx$_*2   # repeated 2n times
[X~]  # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep {                },  # Filter strings
S:g/             # Globally replace regex match
$$# literal ( <~~> # whole regex matched recursively * # zero or more times$$    #   literal )
//  # with empty string
!                 # Is empty string?


# Retina 0.8.2, 50 bytes

.+
$* 1 11 +%11 <$'¶$> Gm^(?<-1>(<)*>)*$(?(1).)


Try it online! Uses <>s. Explanation:

.+
$*  Convert to unary. 1 11  Double the result. +%11 <$'¶$>  Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>. Gm^(?<-1>(<)*>)*$(?(1).)


Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.

# JavaScript (ES6), 112 102 bytes

This is heavily based on nwellnhof's C answer.

f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(
,i,m=s=0)+f(n,-~i)


Try it online!

# Red, 214, 184 136 bytes

func[n][g: func[b n][either n = length? b[if not error? try[load b][print b]return 0][g append copy b"["n g append copy b"]"n]]g""2 * n]


Try it online!

Uses Jo King's approach. Finds all possilble arrangements of brackes using recursion (they are generated in lexicographic order) and print it if the arrangement evaluates as a valid block.

# Jelly,  15  14 bytes

-1 thanks to ChartZBelatedly! (Use a better fixed-point built-in.)

ḤØ(ṗœṣØ(F$ÐLÐḟ  A monadic Link accepting $$\n\$$ that yields a list of lists of characters. Try it online! (footer formats the list as lines.) ### How? ḤØ(ṗœṣØ(F$ÐLÐḟ - Link: integer, n
Ø(            - literal ['(', ')']
Ḥ              - double (n)
ṗ           - Cartesian power -> all length 2n lists of '(' and/or ')' (already sorted)
ÐL   -   repeat until a fixed point is reached applying:
$- last two links as a monad, f(current, initially proposed): œṣ - split at: Ø( - literal ['(', ')'] F - flatten } -> empty list if balanced (only empty lists are falsey)  • -1 byte as ƬṪ$ can be replaced with ÐL Mar 16, 2021 at 23:00
• @ChartZBelatedly - Ah, I golfed my way from something that then transposed and head-ed. Thanks! Mar 16, 2021 at 23:03

f n=[x|x<-mapM("()"<$f)[1..2*n],0:y<-[scanr(\b->(sum[2|b>'(']-1+))0x],all(>=0)y]  Try it online! # Jelly, 19 bytes Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(


Try it online!

Output clarified over TIO.

# JavaScript (Node.js), 84 bytes

f=(n,s='')=>n?f(n-=.5,s+'[')+f(n,s+']'):[...s].some(t=>(n+=t<']'?1:-1)<0)|n?'':s+



Try it online!

# JavaScript (Node.js), 90 bytes

f=(n,s='')=>n?f(n-=.5,s+'[')+f(n,s+']'):eval("try{eval(s.split+),s+\n}catch(_){''}")


Try it online!

Is it an array?