Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 Michael Press Posts: 2,137 Registered: 12/26/06
Re: make 100 by using 1, 7, 7, 7, 7
Posted: Nov 15, 2007 2:42 AM

> On 2007-11-14 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.

A sane approach to listing the strings
is by branch and bound, keeping track of
parentheses depth.

--
Michael Press

Date Subject Author
11/12/07 dangerousgame95@gmail.com
11/12/07 Thomas Nordhaus
11/12/07 amzoti
11/12/07 quasi
11/12/07 dangerousgame95@gmail.com
11/13/07 magidin@math.berkeley.edu
11/12/07 Thomas Nordhaus
11/12/07 quasi
11/12/07 Joshua Cranmer
11/12/07 Raymond Manzoni
11/13/07 William Elliot
11/13/07 amzoti
11/12/07 David R Tribble
11/12/07 Nat Silver
11/12/07 Raymond Manzoni
11/12/07 Raymond Manzoni
11/13/07 benjamin.a.bartsch@gmail.com
11/13/07 amzoti
11/13/07 David W. Cantrell
11/13/07 magidin@math.berkeley.edu
11/13/07 David W. Cantrell
11/13/07 magidin@math.berkeley.edu
11/13/07 briggs@encompasserve.org
11/13/07 Robert Israel
11/13/07 Dave Seaman
11/13/07 benjamin.a.bartsch@gmail.com
11/13/07 amzoti
11/13/07 David W. Cantrell
11/13/07 Jan Kristian Haugland
11/13/07 Robert Israel
11/13/07 Kira Yamato
11/13/07 Kira Yamato
11/13/07 Robert Israel
11/13/07 amzoti
11/14/07 Thomas Nordhaus
11/15/07 Michael Press
11/14/07 Michael Press
11/15/07 Kira Yamato
11/15/07 Michael Press
11/15/07 Rick Decker
11/13/07 Raymond Manzoni