Python sol'n to qotw 23 (parens)

This is a recursive solution using generators.  The
idea is essentially the same as Bill Tuckers and also
done by Matthew Walton in his Haskell solution (and
perhaps others).

Here's my attempt at describing the algorithm.

A string S can be broken up into two parts,
the left and the right (so S = L + R).

Given an L, it has 'open_count' open parenthesis
and the size of R is 'remaining'.  The parens
are balanaced so it can never be the case that
open_count > remaining

   - If those two are the same value then there are
     'remaining' close parentheses.  Stop.

   - Otherwise you can always have a '(' so
      generate the solution for L' and R' where

        L' = L + '('  (hence open_count' = open_count + 1)
        R' = string of length remainder' = remainder - 1

   - If open_count > 0 then the first character of R
      can also be a ')', so generate the solution for

        L' = L + ')'  (hence open_count' = open_count - 1)
        R' = string of length remainder' = remainder - 1

To generate all possible strings for S of 2*N, start
with L = "" (open_count == 0) and generate all solution
for R (with remainder == 2*N).

Done in the way described means that all the '('
characters are found before ')' so the output is also
in lexical order.

I use Python's generators so unlike Bill's solution
I don't keep much in memory except the generator stack.

The obvious performance boost is to create, say,
4 characters at a time based on some precomputed table.

The command-line options are

   qotw23.py                  -- run the self-tests
   qotw23.py <number>         -- print all solution of size 2*n
   qotw23.py --count <number> -- just print the count


## qotw23.py
# Python solution to the Perl quiz of the week #23
# See http://perl.plover.com/qotw/r/023

def gen(remaining, open_count):
     # If so, I can only have close parens
     if remaining == open_count:
         yield ")" * open_count
     else:
         # I can always have an '('
         for s in gen(remaining-1, open_count+1):
             yield "(" + s
         # Can I have a ')'?
         if open_count > 0:
             for s in gen(remaining-1, open_count-1):
                 yield ")" + s

def qotw23(n):
     if n < 0: raise TypeError, "must use a positive number"
     if n == 0: return []
     return gen(n*2, 0)

### Everything below here is test and driver code

def test():
     if list(qotw23(0)) != [""]:
         raise AssertionError("wrong for 0")
     if list(qotw23(1)) != ["()"]:
         raise AssertionError("wrong for 1")

     expected = """
         (((())))
         ((()()))
         ((())())
         ((()))()
         (()(()))
         (()()())
         (()())()
         (())(())
         (())()()
         ()((()))
         ()(()())
         ()(())()
         ()()(())
         ()()()()
         """.split()
     expected = [s.strip() for s in expected if s.strip()]
     expected.sort()
     got = list(qotw23(4))
     got.sort()
     if expected != got:
         raise AssertionError("different!")


def main(argv):
     args = argv[1:]
     only_count = 0
     if args and args[0] == "--count":
         only_count = 1
         del args[0]

     if not args:
         raise AssertionError("need a count")
     n = int(args[0])

     if only_count:
         count = 0
         for s in qotw23(n):
             count = count + 1
         print count
     else:
         for s in qotw23(n):
             print s

if __name__ == "__main__":
     import sys
     if len(sys.argv) == 1:
         test()
         print "All tests passed."
     else:
         main(sys.argv)


Here's what I get for timings on my 1GHz PowerBook G4.
I tried with both the --count option and by generating
all the output > /dev/null (wanted to see how much I/O
overhead there was).  I ran them on the command-line
so the 0.12s or so is basically the startup costs.

                               Output
                   Count     >/dev/null  Bill's
Size    Count    Time(in s)   (in s)    times
----   ------    ------     ------    ------
  0          0      0.13       0.14      0.08
  1          1      0.12       0.12      0.06
  2          2      0.12       0.12      0.18
  3          5      0.12       0.12      0.06
  4         14      0.12       0.12      0.11
  5         42      0.12       0.12      0.10
  6        132      0.12       0.12      0.09
  7        429      0.13       0.13      0.15
  8       1430      0.15       0.15      0.31
  9       4862      0.22       0.24      0.57
10      16796      0.49       0.54      1.57
11      58786      1.52       1.82      6.04
12     208012      5.41       6.42     19.62
13     742900     22.39      24.77     64.13
14    2674440     90.73      89.12    228.41
15    9694845    291.84     343.68      n/a

Bill's code is about 3 times slower than mine
for large values.  For small value it's hard
to tell because Perl has a quicker startup time
than Python.

Matthew's compiled Haskell noprint time for 12
elements took 1.5 seconds or about 4 times faster.
However, his print > /dev/null version is 3.1
seconds or only twice as fast.

Matthew said the 12 case generated over 200,000
solutions, which is what I get.  I don't see
any other posts which list the sizes.  I
would like to have the double check.

My algorithm is limited by the stack size.  By
default that's 1,000 for Python, so the largest
solution I can generate is slightly under n=500,
compared to Bill's generation of the first
solution for n=1,000,000 :)


					Andrew
					dalke-DxsMES/F/[email protected]