Date: 09/22/05 (Algorithms) Keywords: no keywords So I tried to write a simple program to solve problems like the one posted yesterday. Wasn't as simple as I thought - its not clear how to recognize if two formulas are duplicates of each other. I have some code in python which sort of works, but can use a lot more improvement, if anyone's interested.
The algorithm to generate all possible formula trees is to partition the multi-set of numbers that should be used (in this instance, {3, 3, 8, 8}) into two subsets and recursively call the algorithm on both the subsets. This should be repeated for each possible partition, and for each operator. The overall tree is the operator in question applied to the formulas obtained from the two subsets. I don't know how to handle unary operators, because they can be chained infinitely without "using up" any arguments. Source: http://www.livejournal.com/community/algorithms/65490.html
|