Hello,
I'm trying to find a way to automatically generate templated expressions that list all possible combinations of brackets around mathematical expressions. So e.g. if you have 3 numbers, it would generate something like (A . B . C) ,A . (B . C) , (A . B) . C
and so on for a variable number of numbers.
Hope someone can help !
thx
no, what I meant was that I need some sort of method that I can pass a parameter to that specifies a number and that the method then generates all combinations of brackets with the number of numbers specified as parameter. So as I said in my first post, if I would pass 3 as parameter to that method, it would generate the combinations as in my first post. if i pass 4, it would generate templates for A . B . C . D with all combinations of brackets
> if i pass 4, it would generate templates for A
> . B . C . D with all combinations of brackets
Are your regerring to the Catalan numbers?
For {A,B,C,D} your brackets would look like this:
( ( ( A B ) C ) D )
( ( A ( B C ) ) D )
( ( A B ) ( C D ) )
( A ( ( B C ) D ) )
( A ( B ( C D ) ) )
The examples given by the OP only contain 1 pair of brackets.
My interpretation was this:
/**
C:\>java BTest 3
(AB)C
(ABC)
A(BC)
C:\>java BTest 4
(AB)CD
(ABC)D
(ABCD)
A(BC)D
A(BCD)
AB(CD)
*/
public class BTest {
public static void main(String[] args) {
doit(Integer.parseInt(args[0]));
}
public static void doit(int n) {
char[] arr = new char[n];
for (int i = 0; i < n; i++)
arr[i] = (char) ('A' + i);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
//System.out.println(i + ", " + j);
StringBuffer sb = new StringBuffer();
for (int k = 0; k < n; k++) {
if (k == i) sb.append('(');
sb.append(arr[k]);
if (k == j) sb.append(')');
}
System.out.println(sb);
}
}
}
}
What do you need this for?
/**
C:\>java CTest 2
( A B )
C:\>java CTest 3
( ( A B ) C )
( A ( B C ) )
C:\>java CTest 4
( ( ( A B ) C ) D )
( ( A B ) ( C D ) )
( ( A ( B C ) ) D )
( A ( ( B C ) D ) )
( ( A B ) ( C D ) )
( A ( B ( C D ) ) )
*/
public class CTest {
public static void main(String[] args) {
doit(Integer.parseInt(args[0]));
}
private static void doit(int n) {
String[] arr = new String[n];
for (int i = 0; i < arr.length; i++)
arr[i] = String.valueOf((char) ('A' + i));
group(arr);
}
// starting at the bottom, every consequetive pair is grouped
// e.g. [A, B, C, D] -> [(A B), C, D] -> [((A B) C) ,D] -> [(((A B) C) D)]
// when the array size is one, there is nothing left to group.
private static void group(String[] arr) {
if (arr.length == 1)
System.out.println(arr[0]);
for (int i = 0; i < arr.length - 1; i++) {
String[] arr2 = new String[arr.length - 1];
arr2[i] = "( " + arr[i] + " " + arr[i + 1] + " )";
for (int j = 0; j < i; j++)
arr2[j] = arr[j];
for (int j = i + 2; j < arr.length; j++)
arr2[j - 1] = arr[j];
group(arr2);
}
}
}
> that's it yes. i didn't know of this catalan numbers
> but after reading some more about it now, this is
> indeed what I wanted. do you know how to do this in
> java ?
Yes, but not as nicely as rkippen already did.
And checkout this nice applet: http://www.maths.usyd.edu.au/u/don/code/Catalan/Catalan.html
Good luck.
thx for the info and the code guys. the duplicates is not really a problem, they can be filtered out anyway. i want to use use this method in a small app that i am writing that solves the well known puzzle where you get n numbers and you have to find an exact number or the closest match to a number using only + - * and /. i needed this to make sure that i try all possible combinations using the brackets because of operator precedence rules when evaluating the expression with the Java Expression Parser.
thx again
> Are your regerring to the Catalan numbers?
Good call.
> My solution has duplicates. I am not sure what the best way
> to prevent duplicates is.
The solution below iterates through all solutions using an
step-able divide and conquer method. I have not proven it to
work for all sizes, but it seams to work for as high as my
computer can test it which is n=13. The print out is then
Number of iterations are 208012
Number of unique brackets are 208012
The Catalan number is 208012
And the code.
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
String[] parts = new String[n];
for (int i = 0; i < parts.length; i++) {
parts[i] = String.valueOf((char) ('A' + i));
}
Node root = new Node(parts, 0, parts.length);
int i = 0;
Set all = new HashSet();
do {
all.add(root.toString());
i++;
} while (root.moveNext());
System.out.println("Number of iterations are "+i);
System.out.println("Number of unique brackets are "+all.size());
System.out.println("The Catalan number is "+
factorial(4*n-6,4)/factorial(n,1));
}
public static long factorial(long i, long order) {
if (i<=0) return 1;
return i*factorial(i-order, order);
}
public static class Node {
public String[] _parts;
public int _i;
public int _j;
public int _divider = -1;
public Node _leftChild = null;
public Node _rightChild = null;
public Node(String[] parts, int i, int j) {
_parts = parts;
_i = i;
_j = j;
if (i+1<j) {
_divider = i+1;
_leftChild = new Node(_parts, _i, _divider);
_rightChild = new Node(_parts, _divider, _j);
}
}
public boolean moveNext() {
if (_divider><0) {
return false;
}
if (_leftChild.moveNext()) {
return true;
}
if (_rightChild.moveNext()) {
_leftChild = new Node(_parts, _i, _divider);
return true;
}
if (_divider+1==_j) {
return false;
}
_divider++;
_leftChild = new Node(_parts, _i, _divider);
_rightChild = new Node(_parts, _divider, _j);
return true;
}
public String toString() {
if (_divider<0) {
return _parts[_i];
}
return "("+_leftChild.toString()+_rightChild.toString()+")";
}
}