Problem Description
Create a program to compute Catalan numbers and list the expressions
they represent.
Background & Techniques
An expression generator was needed to implement our version of the
British TV game show, "Countdown",
CountdownPlus.
The game requires that expressions evaluating to a given value be created
from a given set of numbers. Catalan numbers are the key to creating
all possible valid algebraic expressions of a given length. This page explores Catalan
numbers on more detail. We'll start by seeing how to
generate the "templates" for all parenthesized expressions of a given
length.
Given symbols "X" and "Y", generate all possible strings of length 2N
following these two rules:
- The final string must contain the same number of X's and Y's (N of
each).
- As the string is built (or examined) from left to right, the number
Y's can never exceed the number of X's. Or, stated another way:
The number of Y's in any initial segment of the string cannot exceed the
number of X's.
The Nth Catalan number CN, is the number of such strings.
They are named after Belgian mathematician Eugene Catalan. The strings
are called "Dyck" words after German mathematician Walther Van Dyck.
The equation for CN is given by the number of combinations of
2N things taken N at time divided by (N+1). The more difficult problem
is to list all of the templates for a given N. Replacing "X" with "("
and "Y" with ")" gives all valid expression structures containing N sets of
parentheses. If we replace X's with "(" and "Y"s with variable
names. ("a", "b", c", ...), and add one extra variable at then end, we have
the basis for constructing all valid algebraic expressions containing
N+1 variables connected by binary operators (e.g. +, -, x, or /).
That is exactly what this program does. Here is a step by step
example of the process:
- Start with a C3 string, for example,
XYXXYY to represent some 4 variable
expression. Note: For reasons described below, the program
displays "1"s and "0"s instead of "X"s and "Y"s
- Replace X's with left parens and Y's with variable names:
(a((bc
- Add the 4th variable; (a((bcd
- Insert right parens after each variable occurrence after the first
within a level. Addadditional right parentheses at the end to
balance the number of left pearentheses: (a((bc)d))
- Insert operators (we'll use only * operators here):
(a*((b*c)*d)).
This example is one of the 5 "templates" for expressions with 4 variables.
For each of these, the 4 variables can occur in 24, (4!), ways and the
4 common binary operators which occur 3 times (and which may be repeated)
can appear in 64, (43), ways. So altogether there are 7,680
(5x24x64) parenthesized algebraic expressions with 4 variables and 4 binary
operators.
For the Countdown game there are
42 ways to write expressions with 6 variables and 5 operations.
For each of these expression "templates", the 6 variables
(the given constants) may be plugged in
in 720 ways, and the 4 operation choices which may appear in the 5 operation
positions may be
substituted in 1024 ways. That makes more than 3 million
expressions to be evaluated to find all solutions!
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
Notes for programmers:
The trickiest part of writing the code was deciding how to generate the
templates. I decided to use 1 and 0 characters instead of
X and Y
which allowed me to check treat each string as the binary representation of
an integer. Considered this way, all of the templates can be
represented by integers whose binary representation falls between
101010... and 111...000... inclusive and which can be
inspected individually to save those which meet the 2 original rules.
Function IsOK accomplished this. Valid keys are converted back
to binary strings and saved in ListBox1. A pass through
Listbox1(Phase 2) then converts "1"s to left parentheses and "0"
s to variable letters as described in the example above. Procedures
AddRightParens and AddOps add right parentheses and operation
characters to make the final expression template which are saved in
ListBox2.
The number of variable values in generated templates is limited to 9
merely because that is largest template lengths that can be conveniently
displayed.
Running/Exploring the Program