Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
make 100 by using 1, 7, 7, 7, 7
Replies:
41
Last Post:
Nov 15, 2007 6:13 PM




Re: make 100 by using 1, 7, 7, 7, 7
Posted:
Nov 15, 2007 8:06 AM


Michael Press wrote: > In article <2007111501402216807kirakun@earthlinknet>, > Kira Yamato <kirakun@earthlink.net> wrote: > >> On 20071114 21:08:03 0500, Michael Press <rubrum@pacbell.net> said: >> >>> Here is a Perl script that prints out all balanced strings >>> of parentheses. The balanced strings of 2n parentheses >>> can be bijected with the binary trees on n vertices. >>> >>> The script works like this: >>> >>> P_n is the set of balanced strings of 2n parentheses so >>> P_{n+1} = (P_{k}) P_{n  k}. >>> >>> The script is criminally wasteful of time and >>> space, but it is easy to code, an easy to understand. :) >>> >>> ________________________ >>> #!/usr/bin/perl > > [...] > >>> ________________________ >> Nice work with the recursion! > > Thanks. I should have mentioned that the balanced > strings are bijectable with the complete binary > trees on 2n+1 vertices, a more relevant structure.
Not to mention the triangulations of a convex polygon with n + 2 vertices. > > A sane approach to listing the strings > is by branch and bound, keeping track of > parentheses depth. >
Regards,
Rick



