Parentheses sequences in lexicographical order

Question

^{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

Task

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. — Luis felipe De jesus Munoz, Commented Nov 6, 2018 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example — Jo King, Commented Nov 6, 2018 at 14:13
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge) — user202729, Commented 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) — user202729, Commented 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)? — Jonathan Allan, Commented Nov 6, 2018 at 19:51

Jo King · Accepted Answer · 2018-11-06 22:53:35Z

9

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

edited Nov 6, 2018 at 22:53

answered Nov 6, 2018 at 14:20

Jo King♦

47.5k5 gold badges125 silver badges186 bronze badges

3

\$\begingroup\$ 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. \$\endgroup\$
– nwellnhof
Commented Nov 7, 2018 at 10:48

Add a comment |

J.Doe · Accepted Answer · 2018-11-23 10:33:31Z

R, 112 107 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.

Via http://rachbelaid.com/recursive-regular-experession/

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. — Giuseppe, Commented Nov 7, 2018 at 20:03

ngn · Accepted Answer · 2021-08-06 19:40:06Z

5

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

edited Aug 6, 2021 at 19:40

answered Nov 22, 2018 at 18:19

ngn

15.3k2 gold badges43 silver badges87 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

05AB1E, 13 bytes

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

Try it online or verify some more test cases.

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 6, 2018 at 14:29

Kevin Cruijssen

131k13 gold badges144 silver badges384 bronze badges

Add a comment |

nwellnhof · Accepted Answer · 2018-11-06 19:59:53Z

C (gcc), 114 bytes

f(n,x,s,a,i){char b[99]={};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[99]={};   // 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.
}

TFeld · Accepted Answer · 2018-11-08 07:46:06Z

4

Python 2, 91 88 84 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}

edited Nov 8, 2018 at 7:46

answered Nov 6, 2018 at 14:27

TFeld

19.9k3 gold badges20 silver badges63 bronze badges

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

Add a comment |

G B · Accepted Answer · 2018-11-06 15:19:41Z

3

Ruby, 70 bytes

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

Try it online!

answered Nov 6, 2018 at 15:19

G B

22.8k1 gold badge20 silver badges53 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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 /<>/

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 6, 2018 at 14:41

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

nwellnhof · Accepted Answer · 2018-11-06 16:40:48Z

2

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.

edited Nov 6, 2018 at 16:40

answered Nov 6, 2018 at 16:05

nwellnhof

10.6k1 gold badge19 silver badges38 bronze badges

Add a comment |

nwellnhof · Accepted Answer · 2018-11-06 20:07:52Z

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?

Neil · Accepted Answer · 2018-11-07 00:08:01Z

2

Retina 0.8.2, 50 bytes

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

Try it online! Uses <>s. Explanation:

.+
$*

Convert to unary.

1
11

Double the result.

+%1`1
<$'¶$`>

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.

answered Nov 7, 2018 at 0:08

Neil

177k12 gold badges74 silver badges281 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 6, 2018 at 14:32

Arnauld

198k20 gold badges179 silver badges649 bronze badges

Add a comment |

Galen Ivanov · Accepted Answer · 2018-11-23 08:15:47Z

2

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.

edited Nov 23, 2018 at 8:15

answered Nov 6, 2018 at 15:22

Galen Ivanov

21.2k3 gold badges24 silver badges61 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2021-03-16 23:08:17Z

2

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)
            Ðḟ - filter discard if:
          Ð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)

edited Mar 16, 2021 at 23:08

answered Mar 16, 2021 at 22:58

Jonathan Allan

110k7 gold badges65 silver badges282 bronze badges

\$\begingroup\$ -1 byte as ƬṪ$ can be replaced with ÐL \$\endgroup\$
– caird coinheringaahin g ♦
Commented Mar 16, 2021 at 23:00
1

\$\begingroup\$ @ChartZBelatedly - Ah, I golfed my way from something that then transposed and head-ed. Thanks! \$\endgroup\$
– Jonathan Allan
Commented Mar 16, 2021 at 23:03

Add a comment |

Delfad0r · Accepted Answer · 2022-01-14 15:59:50Z

2

Haskell, 80 bytes

f n=[x|x<-mapM("()"<$f)[1..2*n],0:y<-[scanr(\b->(sum[2|b>'(']-1+))0x],all(>=0)y]

Try it online!

answered Jan 14, 2022 at 15:59

Delfad0r

6,27619 silver badges32 bronze badges

Add a comment |

Erik the Outgolfer · Accepted Answer · 2018-11-06 17:53:16Z

1

Jelly, 19 bytes

Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(

Try it online!

Output clarified over TIO.

answered Nov 6, 2018 at 17:53

Erik the Outgolfer

40.6k5 gold badges45 silver badges122 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2021-03-19 05:41:58Z

1

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?

edited Mar 19, 2021 at 5:41

answered Mar 19, 2021 at 5:20

l4m2

28.3k2 gold badges25 silver badges103 bronze badges

Add a comment |

Stack Exchange Network

Parentheses sequences in lexicographical order

17 Answers 17

Perl 6, 36 bytes

Explanation:

R, 112 107 99 bytes

Explanation

R, 107 bytes

K (ngn/k), 36 35 37 bytes

05AB1E, 13 bytes

C (gcc), 114 bytes

Explanation

Python 2, 91 88 84 81 bytes

Ruby, 70 bytes

Japt, 15 13 bytes

Explanation

Perl 5 `-n`, 41 39 bytes

Perl 6, 42 bytes

Explanation

Retina 0.8.2, 50 bytes

JavaScript (ES6), 112 102 bytes

Red, 214, 184 136 bytes

Jelly, 15 14 bytes

How?

Haskell, 80 bytes

Jelly, 19 bytes

JavaScript (Node.js), 84 bytes

JavaScript (Node.js), 90 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
balanced-string
or ask your own question.

Linked

Hot Network Questions

Parentheses sequences in lexicographical order

17 Answers 17

Perl 6, 36 bytes

Explanation:

R, 112 107 99 bytes

Explanation

R, 107 bytes

K (ngn/k), 36 35 37 bytes

05AB1E, 13 bytes

C (gcc), 114 bytes

Explanation

Python 2, 91 88 84 81 bytes

Ruby, 70 bytes

Japt, 15 13 bytes

Explanation

Perl 5 -n, 41 39 bytes

Perl 6, 42 bytes

Explanation

Retina 0.8.2, 50 bytes

JavaScript (ES6), 112 102 bytes

Red, 214, 184 136 bytes

Jelly, 15 14 bytes

How?

Haskell, 80 bytes

Jelly, 19 bytes

JavaScript (Node.js), 84 bytes

JavaScript (Node.js), 90 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfbalanced-string or ask your own question.

Linked

Related

Hot Network Questions

Perl 5 `-n`, 41 39 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
balanced-string
or ask your own question.