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 ]
 Kira Yamato Posts: 526 Registered: 7/2/05
Re: make 100 by using 1, 7, 7, 7, 7
Posted: Nov 15, 2007 1:40 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
>
> \$count = \$ARGV[0];
>
> print join "\n", pren(\$count), "";
>
> sub pren
> {
> my @list = ();
>
> (my \$n) = @_;
> if (\$n == 0) {push(@list, "")}
> elsif(\$n == 1) {push(@list, "()")}
> elsif(\$n > 1)
> {
> foreach \$k (0 .. \$n-1)
> {
> foreach \$p1 (pren(\$k))
> {
> foreach \$p2 (pren(\$n - 1 - \$k))
> {
> push @list, sprintf "(%s)%s", \$p1, \$p2;
> }
> }
> }
> }
> return @list;
> }
> ________________________

Nice work with the recursion!

>
>
> \$ ./parens.pl 5 | cat -n
> 1 ()()()()()
> 2 ()()()(())
> 3 ()()(())()
> 4 ()()(()())
> 5 ()()((()))
> 6 ()(())()()
> 7 ()(())(())
> 8 ()(()())()
> 9 ()((()))()
> 10 ()(()()())
> 11 ()(()(()))
> 12 ()((())())
> 13 ()((()()))
> 14 ()(((())))
> 15 (())()()()
> 16 (())()(())
> 17 (())(())()
> 18 (())(()())
> 19 (())((()))
> 20 (()())()()
> 21 (()())(())
> 22 ((()))()()
> 23 ((()))(())
> 24 (()()())()
> 25 (()(()))()
> 26 ((())())()
> 27 ((()()))()
> 28 (((())))()
> 29 (()()()())
> 30 (()()(()))
> 31 (()(())())
> 32 (()(()()))
> 33 (()((())))
> 34 ((())()())
> 35 ((())(()))
> 36 ((()())())
> 37 (((()))())
> 38 ((()()()))
> 39 ((()(())))
> 40 (((())()))
> 41 (((()())))
> 42 ((((()))))

--

-kira

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