Recursion bracketed; or Dyck words generation

Question

We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…

A Dyck word is a string, of length 2n, consisting of n opening and n closing parentheses (( and )) fully matched (that is to say: for all prefixes of the string, the number of opening parentheses is greater than or equal to the number of closing ones).

It is interesting to note that the number of different Dyck words of length 2n is equal to the (n + 1)-th Catalan number.

It’s pretty straightforward to write a program that generates these words with a recursive function. But the goal here is to do the same thing without.

Challenge

Write a full program or function that takes a positive integer, n, using stdin or an acceptable alternative, and outputs all the different Dyck words of length 2n. The words can appear in any order and each must be separated from each other by a line break. Moreover, your program should not use recursive functions (see details below).

Rules

• The output of your program should only contain Dyck words of length 2n, separated by line breaks. Each word must appear only once.
• Your program must work at minimum for inputs 0 to 15.
• You may not write recursive functions, neither direct (a function that calls itself) nor indirect (e.g. a function f that calls another function g that calls function f). That being said, you can still use the standard functions of your language without worry of how they work internally.
• Similarly, your program should not call itself.
• You may not use non-standard librairies.
• Your program may not read or write files.
• Your program must be able to run in a reasonable time for 0 ≤ n ≤ 15 (hence, naively generate all arrangements is probably not a good idea). Let’s say less than 20 minutes with a memory limit of 4 GB (my reference implementation in C manages n = 15 in less than 5 seconds).
• All standard loopholes are forbidden.

As usual in code-golf, the shortest code in bytes wins. But if you have found an interesting way to achieve this challenge in your language, please do not hesitate.

Test I/O

For this input:

3

The output could be (any other order is correct too):

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

Answer 1

C99, 105 bytes

i,j,s;f(n){for(char a[31]={};++i%(1<<2*n);s||puts(a))for(j=s=0;~s&&j<2*n;)s+=1-(a[j]=40+(i>>j++)%2)%2*2;}

Iterates over all strings of 2n parentheses.

With piped output and compiler flag -O3, input n = 15 takes roughly 15.5 seconds on my machine. Memory consumption is 1.2 MB.

Test it on Ideone.

Answer 2

Pyth, 26 23 bytes

jeuaGsMs*VjRL`()_GGQ]]k

Try it online

                    ]]k   starting at G=[['']],
  u                Q      repeat the given number of times:
                _G          reversed G
          jRL`()            parenthesize each level-2 element
        *V        G         take Cartesian products of corresponding
                              elements of that and G
       s                    concatenate, yielding a list of pairs
     sM                     concatenate each resulting pair
   aG                       append the resulting list to G
je                        finally, join the last result on newlines

This directly follows the Catalan recurrence (with a non-recursive dynamic programming implementation) and doesn’t use any filtering. On my laptop, it runs in 55 seconds using 2.67 GiB RAM for n = 15.

Pyth, 33 bytes, O(n) memory

=S*Q`()Wn2J+3x
Q"(()"=+.<S<QJ1>QJ

Try it online

  *Q`()                  build a string with Q copies of "()"
 S                       sort it
=                        assign it to Q

       W                 while the following is true:
(newline)                  print Q
Q
             x             take the index of the first occurrence of "(()"
 "(()"
           +3              add 3
          J                assign to J
        n2                 is this not equal to 2 (i.e. was "(()" found)?
                         do the following:
           <QJ             take the first J characters of Q
          S                sort them
        .<    1            cyclically shift them left by 1
       +       >QJ         add the remaining characters of Q
      =                    assign to Q

This algorithm outputs all Dyck words in a stream, with each word being generated from the previous one and no additional state. On my laptop, it runs in 170 seconds using basically no RAM for n = 15.

As an example illustrating how it works:

()()()()((()()(())))(())
         ^^^               becomes
(((((()))))(()(())))(())

Similarly computing the words in the reverse of this order also takes 33 bytes:

=*QK`()WJhx
Q_K=+t.iFc2_<QJ+K>QhJ

Try it online

Answer 3

CJam (48 bytes)

ri"()"*${_p_,{1$>_)-,\(-,<},_{W=/(\s$1m>+}{&}?}h

Online demo. This effectively takes one obvious recursive solution and makes it iterative. Instead of actually simulating the steps back up the stack, it applies a successor rule:

Find the last ( which starts a suffix with strictly more ) than (; sort that suffix, and rotate once.

Note that this is deliberately designed to avoid keeping the full list of solutions in memory, because I don't think it fits (at least, not if run on a 64-bit machine. It might on a 32-bit machine). There are 9694845 Dyck paths for n=15, so that's 30*9694845 characters, and 92*9694845 = 891925740 bytes of memory just for the (Java) String objects. But then the List holding the objects probably wraps an array with space for 16777216 elements, which is a further 256MB, and the CJam interpreter itself seems to add quite a bit of overhead.

---

(42 bytes)

Ma{{_'(+\')+}%{"()"\f{\-,}I+_$=},}ri:I2**,

This builds the strings up one character at a time, filtering to ensure that no string has more than n opening parentheses or more closing than opening parentheses. However, it runs out of memory with 3GB for n=15.

The same idea at 39 bytes, but this runs out of memory earlier.

Ma{"()":Sm*::+{S\f{\-,}I+_$=},}ri:I2**`

Online demo

---

(24 bytes)

My original answer, now disqualified by rule changes.

{"()"*e!{0\+{~_}*]1&!},}

This is an anonymous function which takes input on the stack. Online demo.

It works by the obvious approach of taking all permutations of n pairs of parentheses and filtering for those which are balanced.

Answer 4

JavaScript (ES6), 125 bytes

n=>{for(i=m=1<<n+n-1;i&m;i++){for(j=m,z=o=0;o>=z;j>>=1)i&j?o++:z++;o-n||console.log(i.toString(2).replace(/./g,d=>")("[d]))}}

Actually printing the results slows things down horribly, but with console.log set to ()=>{} this takes my machine about 7 seconds for n=12, which presumably translates to 7 minutes for n=15. If that's not fast enough, you can replace i++ with i+=2 or even i+=j||2 but that made only a few percent difference in my testing. Works by generating all 2n-digit binary numbers and checking whether they represent a Dyck word. Ungolfed:

function dyck(n) {
    // Don't bother generating words that begin with ),
    // so start half-way though 4 ** n.
    for (var i = 4 ** n / 2; i < 4 ** n; i += 2) {
        // Convert to the string of ()s.
        var word = i.toString(2);
        word = word.replace(/1/g, "(");
        word = word.replace(/0/g, ")");
        // Count the (s and )s separately.
        var left = 0;
        var right = 0;
        for (var j = 0; j < n + n; j++) {
            if (word[j] == "(") left++;
            else right++;
            // Abort if there are too many )s
            if (right > left) break;
        }
        // If we got exactly n (s then it's a Dyck word.
        if (left == n) console.log(word);
    }
}

Answer 5

C, 748 746 651 bytes

#define C(v,n) for(v=n==D;v<=(n<=D);v++)
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2){R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|e<<5|d<<4|c<<3|b<<2|a<<1;if(__builtin_popcount(R)!=Z)goto X;F=0;for(E=D-1;E;E--)if(R&1<<E)F++;else if(F)F--;else goto X;for(;E<D;E++)putchar(40+!(R&1<<D-E-1));puts("");X:;}}

At a whopping >600 bytes, this isn't really much of a contender...but it's pretty fast and memory efficient.

Works by encoding the parentheses strings as integers, with a set bit representing ( and an unset bit representing ). For instance, (()) would be 1100. I made the following observations:

• All permutations must begin with ( and end with ); otherwise, it won't be valid.
• Every valid permutation must have n left parentheses and n right parentheses, where n is the input number. I used __builtin_popcount for this.

When built via icc -march=native -O3, it takes 17s on my computer, though others have reported better times (~3-7s) on their (presumably faster) computers. In addition, it uses around 1.5 KB of memory.

Here's the code with explanatory comments:

// Z is the input number.
void p(Z){
    // All the variables.
    // R is the resulting paren number, with 1 bits for open parens and 0s for closed ones.
    // a-C are used to hold the state of each paren (1 if open, 0 if closed).
    // D holds Z*2, or the total length of the paren string.
    // E and F are used later on.
    unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;
    /* Each loop performs a basic check. If D is equal to the corresponding
       number, then the variable will start at 1 (since the first paren must
       always be open). If D is greater than or equal to the number, then the loop
       will only be run once with the variable set to 0, and a later check will
       cause the variable to be ignored. Otherwise, it will loop twice; one for a
       closed paren (0), and one for an open one (1). Of course, if D == the
       number, then it will only loop for the open paren (as stated above). */
    for (C = (D == 30); C <= (30 <= D); C++)
    for (B = (D == 29); B <= (29 <= D); B++)
    for (A = (D == 28); A <= (28 <= D); A++)
    for (z = (D == 27); z <= (27 <= D); z++)
    for (y = (D == 26); y <= (26 <= D); y++)
    for (x = (D == 25); x <= (25 <= D); x++)
    for (w = (D == 24); w <= (24 <= D); w++)
    for (v = (D == 23); v <= (23 <= D); v++)
    for (u = (D == 22); u <= (22 <= D); u++)
    for (t = (D == 21); t <= (21 <= D); t++)
    for (s = (D == 20); s <= (20 <= D); s++)
    for (r = (D == 19); r <= (19 <= D); r++)
    for (q = (D == 18); q <= (18 <= D); q++)
    for (p = (D == 17); p <= (17 <= D); p++)
    for (o = (D == 16); o <= (16 <= D); o++)
    for (n = (D == 15); n <= (15 <= D); n++)
    for (m = (D == 14); m <= (14 <= D); m++)
    for (l = (D == 13); l <= (13 <= D); l++)
    for (k = (D == 12); k <= (12 <= D); k++)
    for (j = (D == 11); j <= (11 <= D); j++)
    for (i = (D == 10); i <= (10 <= D); i++)
    for (h = (D == 9); h <= (9 <= D); h++)
    for (g = (D == 8); g <= (8 <= D); g++)
    for (f = (D == 7); f <= (7 <= D); f++)
    for (e = (D == 6); e <= (6 <= D); e++)
    for (d = (D == 5); d <= (5 <= D); d++)
    for (c = (D == 4); c <= (4 <= D); c++)
    for (b = (D == 3); b <= (3 <= D); b++)
    for (a = (D == 2); a <= (2 <= D); a++) {
        /* R is the result here. Each variable is shifted and bitwise-ORd with the
           others to generate a number representing the string.

           For instance, (()) would be 1100, and ()(()) would be 101100. */
        R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|
          q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|
          e<<5|d<<4|c<<3|b<<2|a<<1;
        // If there is an uneven balance of parens, then just jump to the loop end.
        if(__builtin_popcount(R)!=Z) goto X;
        // F here is the number of opening parens.
        F=0;
        // E is a counter used to extract each bit.
        for(E=D-1;E;E--)
            // If the bit is set, then increment the number of open parens.
            if(R&1<<E) F++;
            // If the bit wasn't set, then decrement the number of open parens...
            else if(F) F--;
            // ...but, if there were no open parens, then it's unbalanced; jump to the end
            else goto X;
        // E (the bit counter) is already 0.
        // Loop through each bit...
        for(;E<D;E++)
            /* ...and print it out. 40 is the ASCII code for `(`. If the bit
               is set, the ! will negate it, and 0 will be added to the `(`.
               Otherwise, it will turn the left paren into a right paren. */
            putchar(40+!(R&1<<D-E-1));
        // Newline.
        puts("");
        // End of loop.
        X:;
    }
}

746-byte version

#define C(v,n) for(v=(n==D);v<=(n<=D);v++){
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2)R=(C<<29)|(B<<28)|(A<<27)|(z<<26)|(y<<25)|(x<<24)|(w<<23)|(v<<22)|(u<<21)|(t<<20)|(s<<19)|(r<<18)|(q<<17)|(p<<16)|(o<<15)|(n<<14)|(m<<13)|(l<<12)|(k<<11)|(j<<10)|(i<<9)|(h<<8)|(g<<7)|(f<<6)|(e<<5)|(d<<4)|(c<<3)|(b<<2)|(a<<1);if(__builtin_popcount(R)!=Z)continue;F=0;for(E=D-1;E;E--)if(R&(1<<E))F++;else if(F)F--;else goto X;for(;E<D;E++)putchar('('+!(R&(1<<D-E-1)));puts("");X:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Answer 6

Python 2, 117 116 bytes

def f(n):r='',;exec"r=[s+c for s in r for t in[s.count('(')]for c in')('[t+t==len(s):2-t/n]];"*2*n;print'\n'.join(r)

This builds the strings character by character, without filtering.

With piped output and input n = 15, this takes roughly 39 seconds with CPython and 7.5 seconds with PyPy on my machine. Memory consumption is 1.6 GB with CPython and 2.5 GB with PyPy.

Test it on Ideone.

Answer 7

JavaScript (ES6), 203

Implementing this algorithm (point 3, totally iterative)

Within the limits of script executing in Firefox, I managed to have the 200K console output for input 12 in about 1.5 minutes

n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

Less golfed

n=>{
  b=[...Array(n)].map((_,i)=>1+2*i)
  q=0
  for(z=0;!z;)
  {
    c=[...'('.repeat(n+n)],
    b.map(n=>c[n]=')'),
    console.log(++q,c.join``)
    for(z=i=n;i--&&z;)
      if(b[i]<n+i)
        for(z=0,b[j=i]++;++j<n-1;)
          b[j]=Math.max(b[j-1],2*j)+1
  }
}

Ported to C just for fun, run in 5 secs for input 15 (it compiles and works without #includes)

f(n){int i,j,z,b[49];char c[99];
for(i=n;i--;)b[i]=2*i+1;
for(z=0;!z;){memset(c,40,n+n);c[n+n]=0;
for(i=n;i--;)c[b[i]]=41;puts(c);
for(z=i=n;i--&&z;)if(b[i]<n+i)for(z=0,b[j=i]++;++j<n;)b[j]=(b[j-1]>2*j?b[j-1]:2*j)+1;
}}

Test generating all output but do not display it, just counting output rows

I got 90 sec for input 15

F=n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

console.log=x=>o++ // console.log display no output, just count rows

function test() {
  n=+I.value,o=0,t=+new Date
  O.textContent='...wait...'
  setTimeout(_=>(F(n),O.textContent=['rows='+o,'time sec '+(new Date-t)/1000]), 10)
  
}

test()

N:<input id=I value=12 type=number max=20><button onclick='test()'>go</button>
<pre id=O></pre>

Answer 8

J, 97 70 69 68 60 59 bytes

'()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]

Now tacit!

This is a monad that uses binary digits to create pairs of parentheses. In order to meet the requirements, a non-recursive approach is used along with optimization by use of certain primitives to ensure that mostly boolean (1 byte) values are used to keep memory requirements low.

On my computer, using an i7-4770k, it takes about 50 seconds to compute the result for n = 15 and uses about 1.5 GB of memory.

In the interests of maximizing speed, this version with 70 bytes computes the result for n = 15 in 0.5 seconds while using about 800 MB of memory. It's also tacit!

'()'{~[:;@(<@([:,/],"1/0=|."1)/.~+/"1)<:1&(],(+/<:#-+/)"1@,.~#,.~)1$0:

Usage

   f =: '()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]
   timer =: 6!:2
   f 3
()()()
(())()
()(())
(()())
((()))
   10 timer 'r =: f 15'  NB. Average time over 10 runs
49.9951
   # r
9694845

Answer 9

Pyth, 47 bytes

                                                               <-empty line
Musm?<J/d\(Q?>-J/d\)0,+d\(+d\)]+d\(]+d\)G*2Q]k

Took 18 minutes on my machine, and over 2GB RAM.

In pythonic pseudocode:

// newline means "print"
M                                              map(print,
 u                                               reduce(lambda G,H:
  sm                                               sum(map(lambda d:
                     ,+d\(+d\)                       ([d+"(",d+")"] if
            ?>-J/d\)0                                   J-d.count(")") > 0
                              ]+d\(                     else [d+"("]) if
    ?<J/d\(Q                                           (J=d.count("(") < Q
                                   ]+d\)               else [d+")"],
                                        G              G)),
                                         *2Q]k     2*input(),[""]))

In words:

1. create a function that maps any string to a list of strings that can be formed by adding "(" or ")"
   if the parentheses are already matched, only "(" can be added; if there are already n "(", only ")" can be added; otherwise a pair is returned
2. create a new function that maps the old function over its param, and then sum up the map, so that it takes a list of strings, maps to a list of lists of strings, and then de-nests it back into a list of strings
   each call essentially "grows" its params by one ( or )
3. reduce this new function over range(2*input()), with [""] as base case
   essentially just passing [""] through the new function 2n times
4. map print over the return value of reduce to print each string in new lines

Answer 10

Haskell, 111 105 bytes

import Data.Function
id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1])

Usage example: id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1]) $ 3 -> ["((()))","(()())","(())()","()(())","()()()"].

The Dyck word building algorithm used here expressed in a classic recursive way looks like

dyck a z =                    -- take two numbers, `a` (the number of `(` to use)
                              -- and `z` (the number of `)` to use)
                 [[""]|a+z<1] -- base case if both numbers are 0, the result
                              -- is an empty word
    [('(':)<$>dyck(a-1)z|a>0] -- if there are `(` left, prepend one to every result
                              -- from a recursive call with one `(` less
   [(')':)<$>dyck a(z-1)|a<z] -- same for `)` if there are more than `(`.
id=<<  ...  ++  ...  ++       -- combine those results in to a flat list

As recursion is not allowed, we pass the function to call as a third parameter h (and use a lambda instead of a named function):

\h a z ->   ....  h(a-1)z  ....  h a(z-1)

and let the fixpoint combinator fix create this function for us:

fix(\h a z ...)

finally, the leftmost id=<< duplicates the input parameter: (id=<<) f n is f n n, so when the whole function is called, the parameter n is used as a and z.

For input 15 it takes about 3min within ghci (25s when compiled) and a few MB on my 5 year old laptop.

Answer 11

Haskell, 140 132 bytes

Thanks @nimi for saving a few bytes!

import Data.List
h s|m<-length s=nub[k|l<-s!!0,k<-('(':l++")"):[u++v|n<-[0..m-2],u<-s!!n,v<-s!!(m-2-n)]]:s
f n=iterate h[[""]]!!n!!0

First of all: iterate does create a recursion sequecnce of h, but this is a builtin, and by the rules we may use builtins that use recursion.

This is just a very simple recursive approach, we can generate the n-Dyck-words by putting (n-1)-Dyck-words between paranthesis, or by concatenating from shorter Dyck words. This approach however does generate duplicates, that is why we filter for unique elements using nub.

As Haskell is a functional language, it is almost impossible to do this without recursion. There is an even more direct approach, but that one is banned under the current rules.