9
\$\begingroup\$

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

    (())
    ()()
    
\$\endgroup\$
  • \$\begingroup\$ @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge. \$\endgroup\$ – Luis felipe De jesus Munoz Nov 6 '18 at 14:12
  • \$\begingroup\$ Eh, I can think of a few languages where eval would interpret them differently for example \$\endgroup\$ – Jo King Nov 6 '18 at 14:13
  • 1
    \$\begingroup\$ Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge) \$\endgroup\$ – user202729 Nov 6 '18 at 14:23
  • 3
    \$\begingroup\$ 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) \$\endgroup\$ – user202729 Nov 6 '18 at 14:24
  • \$\begingroup\$ 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)? \$\endgroup\$ – Jonathan Allan Nov 6 '18 at 19:51

14 Answers 14

8
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\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 Nov 7 '18 at 10:48
5
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Nov 7 '18 at 20:03
4
\$\begingroup\$

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.
}
\$\endgroup\$
4
\$\begingroup\$

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

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

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
\$\endgroup\$
3
\$\begingroup\$

Ruby, 70 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 36 bytes

{"()"(&/-1<+\1-2*)#(x=+/)#+!(2*x)#2}

Try it online!

+!(2*x)#2 all binary vectors of length 2*n

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

(&/-1<+\1-2*)# only those whose partial sums, treating 0/1 as 1/-1, are nowhere negative

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

\$\endgroup\$
3
\$\begingroup\$

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 /<>/
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 19 bytes

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

Try it online!

Output clarified over TIO.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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