Algorithm analysis of "24 points"
wedge
Some people in the forum have asked how to write a calculation of 24 points. I think this topic is very interesting, so I wrote one. Although this program can also run, and have also helped two colleagues to solve their children's homework, but I am not satisfied. The reason is very simple: it can list the possible combinations, but this is just the result I pre-analyzed. If the number given is not 4, but 5 or 6, this program is completely scrapped. More importantly, if there are 5, 6 or more numbers, the method of prior analysis is not available. So I must find a real algorithm.
Analysis of Algorithms
The basic operation is only four, plus, minus, multiplication, divided. Therefore, no matter how complicated a calculation, we can always summarize it into a basic addition and subtraction, except, just a simple number on the left and / or right side of the operator, but a complicated calculation. So, our first task is to disassemble a collection into two collections and enumerate all the possibilities.
Split collection
First of all, you must declare that the collection is actually not accurate. There is no repetitive element in the collection, but the number of 24 points can be repeated. However, because the idea of this algorithm is derived from the collection, I still call it "split split".
So how can I remove a collection, and enumerate all the possibilities? We all know that if a collection has n elements, then it will have 2 ** n subsets [1]. Because of the multiplication principles of the arrangement, each element has two states, which belongs or not. Therefore, n elements will have 2 ** n subsets. then:
Def EnumerateAllSubsets (Elements):
Def appendelement (Orig_Subsets, Element):
Result = []
For set in orig_subsets:
Result.Append (SET)
TMP = []
For ELE IN SET:
TMP.Append (ELE)
TMP.Append (Element)
Result.Append (TMP)
Return RESULT
Result = [[]]]
For e in Elements:
Result = appendelement (Result, E)
For e in Result:
e.sort ()
Return RESULT
The idea of this program is this: Assumption has a collection, its subset collection is orig_subsets, then after this collection adds an element ELEMENT, the appendelement method is responsible for returning the subset of this new collection. ENUMERATEALLSUBSETS first creates a collection that contains only empty sets. This only set the set of empty sets is the subset of empty sets. Then we will add an element in the empty set and use the appendelection to get the collection of its subset. So after we add Elements all in turn, we have obtained the collection of Elements.
ENUMERATEALLSUBSETS returned to the subset of subset cannot be used directly on 24 points, so we must do some preparations first - remove empty sets and complete works. Since there may be repetitive numbers in the collection, we have to remove the repeated subset in order to reduce the amount of operation.
DEF GetSets (Elements):
Elements.sort ()
TMP_RESULT = EnumerateAllSubsets (Elements)
TMP_RESULT.Remove ([])
TMP_RESULT.REMOVE (Elements)
Result = []
For e in tmp_result: E.SORT ()
TRY:
Result.index (e)
Except ValueError:
Result.Append (e)
Return RESULT
In addition, we also need a function of calculating a supplement.
DEF Suppset (Fullset, Subset):
Result = []
For item in fullset: # Since there is a repetitive element, you can't write
Result.Append (item) # for item in fullset:
For item in subset: # if not item in subs:
Result.remove (item) # Result.Append (item)
Return RESULT
Constructor
For this algorithm, the structure of the calculation is not difficult, but I am annoying. Below we use the binary tree to represent the calculation, deliver value and printing with the return.
Add = " "
Min = "-"
Mul = "*"
DIV = "/"
TYPE_OF_NUMBERS = (Type (1), Type (1.0))
Class EquationTree (Object):
DEF __INIT__ (Self, Left_Tree, Operator = none, right_tree = none):
Self.Left_tree = left_tree
Self.right_tree = Right_Tree
Self.operator = Operator
DEF Value (Self):
IF not self.operator:
Return float (Self.LEFT_TREE)
Else:
if Type (Self.Left_Tree) in type_of_numbers:
STR_TO_CALC = Str (FLOAT (Self.left_tree))
Else:
STR_TO_CALC = STR (Self.Left_tree.Value ())
STR_TO_CALC = SELF.OPERATOR
if Type (Self.right_tree) in type_of_numbers:
STR_TO_CALC = Str (Float (Self.right_tree))
Else:
STR_TO_CALC = Str (Self.right_tree.Value ())
TRY:
## 1. When ZerodiveRrou, this calculation value is NONE.
## 2. This value of this calculation is None, then this calculation value is NONE
Result = evAl (STR_TO_CALC)
Except:
Result = none
Return RESULT
DEF __REPR__ (Self):
if Type (Self.Left_Tree) in type_of_numbers:
LEFT_REPR = Str (Self.left_tree)
Else:
LEFT_REPR = `Self.Left_tree`
if Type (Self.right_tree) in type_of_numbers:
Right_repr = Str (Self.right_tree)
Else:
Right_repr = `Self.right_tree`
IF not self.operator:
Return LEFT_REPR
Else:
If self.operator == add: pass
Elif self.operator == min:
If Type (Self.right_tree) Not in type_of_numbers and self.right_tree.operator in (add, min):
Right_repr = "(" Right_repr ")"
Elif self.operator == MUL:
if Type (Self.left_tree) Not in Type_Of_NumBers and Self.Left_tree.operator In (Add, Min):
LEFT_REPR = "(" LEFT_REPR ')'
If Type (Self.right_tree) Not in type_of_numbers and self.right_tree.operator in (add, min):
Right_repr = "(" Right_repr ')'
Else:
if Type (Self.right_tree) Not in Type_Of_Numbers and self.right_tree.operator:
Right_repr = "(" Right_repr ')'
If IPE_OF_NUMBERS AND (SELF.LEFT_TREE.Ope In (Add, Min):
LEFT_REPR = "(" LEFT_REPR ')'
Return LEFT_REPR SELF.Operator Right_repr
Enumerate
Next we use the two tools prepared above to enumerate all the formulas. Still use of recursive.
Def getEQTREES (ELEMENTS):
IF LEN (Elements) == 1:
Return [EquationTree (ELEments [0])]]]]]
Elif Len (Elements) == 2:
Return [EquationTree (EQUATIONTREE (ELEments [0], Add, Elements [1]),
EquationTree (Elements [0], Min, Elements [1]),
EquationTree (Elements [0], Mul, Elements [1]),
EquationTree (Elements [0], DIV, Elements [1]),
EquationTree (Elements [1], Min, Elements [0]),
EquationTree (Elements [1], DIV, Elements [0]),]
Else:
Result = []
For e in getsets (Elements):
For Left_Tree In GetEQTREES (E):
For Right_Tree In GetEQTREES (Suppset (Elements, E)):
For OP IN (Add, Min, Mul, Div):
Result.Append (EquationTree)
Return RESULT
end
The program has been roughly completed, and it can run [2] as long as you add a main program.
IF __NAME__ == '__main__':
Print "" "Written By Shghgs, ON March 3, 2004." ""
Result = []
Print "" "
Please Input A Tuple of Integer, Delimited by Colon.
For Example: 1, 2, 3, 4
Don't try to input more Than 5 Numbers,
OtherWise It Will Take A Long Long Time To Respond.
Four is recommended.
"" "
Tup = INPUT ('Please Input the Tuple of Integers:')
For EQ IN GETEQTREES (List (TUP):
if Eq.Value () == 24:
Result.Append (EQ)
PRINT "% s = 24"% EQ
I used four variables and 5 variables to have successful. But 6 variables have not been a result for an hour, and finally I gave up. I think it is probably that the amount is too large. Interested readers can try it. By the way, my test platform is P4 Celeron 2.0G, 1G memory, Windows 2000 SP4. If your configuration is lower than this, it is recommended to try it.
[1] This algorithm is implemented with Python, so the representation of Python here. Interested readers can try to use Java or other languages.
[2] There is a Chinese comment in this program, so warning will appear when running. To solve this problem, you can add:
# - * - CODING: MBCS - * -
