← Back to branch summary

~yacinechaouche/+junk/BZR

« back to all changes in this revision

Viewing changes to CODE/TEST/PYTHON/MATHS/generator_r3.py

  • Committer: yacinechaouche at yahoo
  • Date: 2015-01-14 22:23:03 UTC
  • Revision ID: yacinechaouche@yahoo.com-20150114222303-6gbtqqxii717vyka
Ajout de CODE et PROD. Il faudra ensuite ajouter ce qu'il y avait dan TMP

Show diffs side-by-side

added added

removed removed

Lines of Context:
CODE/TEST/PYTHON/MATHS/generator_r3.py
 
1
## Yassine chaouche
 
2
## yacinechaouche@yahoo.com
 
3
## http://ychaouche.wikispot.org
 
4
## Jun 16 2012 - 16:53
 
5
 
 
6
"""
 
7
This file contains the combo function : a generator that takes numbers
 
8
as parameter (any number of numbers), and generates every possible combination
 
9
of simple algebric expressions with these numbers.
 
10
 
 
11
For example combo([2,4,9]) -> : (108 combinations)
 
12
 
 
13
(2+(4-9)) (2+(4+9)) (2+(4*9)) (2+(4/9)) (2+(9/4)) (2+(9-4)) (4+(9+2)) (4+(9-2)) (4+(9*2))
 
14
(2-(4-9)) (2-(4+9)) (2-(4*9)) (2-(4/9)) (2-(9/4)) (2-(9-4)) (4-(9+2)) (4-(9-2)) (4-(9*2))
 
15
(2*(4-9)) (2*(4+9)) (2*(4*9)) (2*(4/9)) (2*(9/4)) (2*(9-4)) (4*(9+2)) (4*(9-2)) (4*(9*2))
 
16
(2/(4-9)) (2/(4+9)) (2/(4*9)) (2/(4/9)) (2/(9/4)) (2/(9-4)) (4/(9+2)) (4/(9-2)) (4/(9*2))
 
17
((4-9)/2) ((4+9)/2) ((4*9)/2) ((4/9)/2) ((9/4)/2) ((9-4)/2) ((9+2)/4) ((9-2)/4) ((9*2)/4)
 
18
((4-9)-2) ((4+9)-2) ((4*9)-2) ((4/9)-2) ((9/4)-2) ((9-4)-2) ((9+2)-4) ((9-2)-4) ((9*2)-4)
 
19
 
 
20
(4+(9/2)) (4+(2/9)) (4+(2-9)) (9+(2+4)) (9+(2-4)) (9+(2*4)) (9+(2/4)) (9+(4/2)) (9+(4-2))
 
21
(4-(9/2)) (4-(2/9)) (4-(2-9)) (9-(2+4)) (9-(2-4)) (9-(2*4)) (9-(2/4)) (9-(4/2)) (9-(4-2))
 
22
(4*(9/2)) (4*(2/9)) (4*(2-9)) (9*(2+4)) (9*(2-4)) (9*(2*4)) (9*(2/4)) (9*(4/2)) (9*(4-2))
 
23
(4/(9/2)) (4/(2/9)) (4/(2-9)) (9/(2+4)) (9/(2-4)) (9/(2*4)) (9/(2/4)) (9/(4/2)) (9/(4-2))
 
24
((9/2)/4) ((2/9)/4) ((2-9)/4) ((2+4)/9) ((2-4)/9) ((2*4)/9) ((2/4)/9) ((4/2)/9) ((4-2)/9)
 
25
((9/2)-4) ((2/9)-4) ((2-9)-4) ((2+4)-9) ((2-4)-9) ((2*4)-9) ((2/4)-9) ((4/2)-9) ((4-2)-9)
 
26
 
 
27
The abelian operations are not doubled, this means that for the + and for the *
 
28
operations, only a+b and a*b are generated (b*a and b+a are considered duplicates).
 
29
This is not true however for non abelian operations like - and / .
 
30
 
 
31
You can verify that all these combinations are unique, if that sounds amusing to you.
 
32
Some of them may have the same value, but they're not obtained the same way, so they're
 
33
not considered the same. This may seem more obvious to you in large combinations (6 to 9 numbers)
 
34
where one problem may have tens of solutions.
 
35
"""
 
36
 
 
37
def combo(S):
 
38
    """
 
39
    How it works :
 
40
 
 
41
    S is a Serie of numbers (okay, it's just a list...). But for the purposes of our function,
 
42
    it's treated like a Stack (hence the S).
 
43
 
 
44
    If S contains just two numbers, for example 9 and 8, then combo will generate all possible
 
45
    algebric operations with these two numbers, with the help of the _combo function (notice the
 
46
    leading underscore). So for example combo([9,8]) is a list of six items, returned
 
47
    by the helper funciton _combo(9,8) : 
 
48
    
 
49
    (9+8)
 
50
    (9-8)
 
51
    (9*8)
 
52
    (9/8)
 
53
    (8/9)
 
54
    (8-9)
 
55
 
 
56
    If S has more than just two numbers, for example :
 
57
 
 
58
    S = [4,5,8,9,12]
 
59
 
 
60
    then take the first number (4) out of the stack...
 
61
 
 
62
    S = [5,8,9,12]
 
63
 
 
64
    ...and combine it with every combination c of the remaining numbers, which are obtained by simply
 
65
    calling combo recursively on the Stack. These recursive calls will end when there are just
 
66
    two numbers remaining in the stack, because in each call to Combo, one number is removed as we
 
67
    did earlier.
 
68
    
 
69
    So for example (recursive calls) :
 
70
 
 
71
    -> combo([4,5,8,9,12]) is _combo(4,X) for every X in combo([5,8,9,12]) #removes 4 from the stack
 
72
     -> combo([5,8,9,12]) is _combo(5,Y) for every Y in combo([8,9,12]) #removes 5 from the stack
 
73
      -> combo([8,9,12]) is _combo(8,Z) for every Z in combo([9,12]) #removes 8 from the stack
 
74
       -> combo([9,12]) -> _combo(9,12) (all 6 algebric operations).
 
75
       -> the recursion ends here, return all the combinations of 9 and 12
 
76
      -> return all the combinations of [8,9,12]
 
77
     -> return all the combinations [5,8,9,12]
 
78
    -> combine 4 with every combination of [5,8,9,12]
 
79
    
 
80
    Let's take an example with just three numbers : 4,5, and 8.
 
81
    We decide to execute combo([4,5,8])
 
82
 
 
83
    We remove 4 from the stack, and combine it with every combinations of the remaining numbers
 
84
    8 and 5 :
 
85
    
 
86
    combo([4,5,8]) is _combo(4,c) for every c in combo([5,8]).
 
87
 
 
88
    combo([5,8]) : the stack has only two numbers, so its combinations are simply _combo(5,8),
 
89
    a list of 6 combos : (5+8),(5-8),(5*8),(5/8),(8-5),(8/5).
 
90
    (remember that (8*5) and (8+5) are the same as (5*8) and (5+8) so they're not generated.)
 
91
    
 
92
    What we'll do is take every one of these combinations, let's call them c, and make
 
93
    a combination out of 4, the number we took from S earlier, and c. That's what the line
 
94
    
 
95
    _combo(4,c) for every c in combo([5,8])
 
96
 
 
97
    does.
 
98
 
 
99
    _combo(4,c) has also six possibilities (4+c, 4-c, 4*c, 4/c, c-4,c/4), so for each
 
100
    value of c we have 6 possible combinations with 4, and there are 6 values of c,
 
101
    so the total possibilities of _combo(4,c) is 6 * 6 = 36 possible combos : 
 
102
 
 
103
    (4+(5+8)) (4+(5-8)) (4+(5*8)) (4+(5/8)) (4+(8/5)) (4+(8-5))
 
104
    (4-(5+8)) (4-(5-8)) (4-(5*8)) (4-(5/8)) (4-(8/5)) (4-(8-5))
 
105
    (4*(5+8)) (4*(5-8)) (4*(5*8)) (4*(5/8)) (4*(8/5)) (4*(8-5))
 
106
    (4/(5+8)) (4/(5-8)) (4/(5*8)) (4/(5/8)) (4/(8/5)) (4/(8-5))
 
107
    ((5+8)/4) ((5-8)/4) ((5*8)/4) ((5/8)/4) ((8/5)/4) ((8-5)/4)
 
108
    ((5+8)-4) ((5-8)-4) ((5*8)-4) ((5/8)-4) ((8/5)-4) ((8-5)-4)
 
109
 
 
110
    Notice how 4 is always in one side of the operation and (8,5) is on the other side ?
 
111
    There are still many combinations left where 4 is "in the middle" of the expression,
 
112
    not just on its sides. And so does for 5 and 8. 
 
113
 
 
114
    We can simply acheive this by putting 4 back in the stack...
 
115
    
 
116
    S = [4,5,8]
 
117
 
 
118
    take 5 out of it...
 
119
 
 
120
    S = [4,8]
 
121
 
 
122
    and make every combinations of 5 with every combinations of 4 and 8. We get this : 
 
123
 
 
124
    (5+(8+4)) (5+(8-4)) (5+(8*4)) (5+(8/4)) (5+(4/8)) (5+(4-8))
 
125
    (5-(8+4)) (5-(8-4)) (5-(8*4)) (5-(8/4)) (5-(4/8)) (5-(4-8))
 
126
    (5*(8+4)) (5*(8-4)) (5*(8*4)) (5*(8/4)) (5*(4/8)) (5*(4-8))
 
127
    (5/(8+4)) (5/(8-4)) (5/(8*4)) (5/(8/4)) (5/(4/8)) (5/(4-8))
 
128
    ((8+4)/5) ((8-4)/5) ((8*4)/5) ((8/4)/5) ((4/8)/5) ((4-8)/5)
 
129
    ((8+4)-5) ((8-4)-5) ((8*4)-5) ((8/4)-5) ((4/8)-5) ((4-8)-5)
 
130
    
 
131
    Now we put back five in the stack...
 
132
 
 
133
    S = [4,5,8]
 
134
 
 
135
    and remove 8...
 
136
 
 
137
    S = [4,5]
 
138
 
 
139
    Then generate all combinations of 8 with all combinations of 4 and 5.
 
140
 
 
141
    (8+(4+5)) (8+(4-5)) (8+(4*5)) (8+(4/5)) (8+(5/4)) (8+(5-4))
 
142
    (8-(4+5)) (8-(4-5)) (8-(4*5)) (8-(4/5)) (8-(5/4)) (8-(5-4))
 
143
    (8*(4+5)) (8*(4-5)) (8*(4*5)) (8*(4/5)) (8*(5/4)) (8*(5-4))
 
144
    (8/(4+5)) (8/(4-5)) (8/(4*5)) (8/(4/5)) (8/(5/4)) (8/(5-4))
 
145
    ((4+5)/8) ((4-5)/8) ((4*5)/8) ((4/5)/8) ((5/4)/8) ((5-4)/8)
 
146
    ((4+5)-8) ((4-5)-8) ((4*5)-8) ((4/5)-8) ((5/4)-8) ((5-4)-8)
 
147
 
 
148
    Done ! you have cycled through all elements of your stack, and so you have all
 
149
    108 possible combinations of 4,5 and 8 taken in any possible order. If all the
 
150
    numbers are different, all the combinations are unique.
 
151
    
 
152
    Let's analyze this algorithme and see if we're going to explode the memory for
 
153
    high numbers of stack size. Here's how our algorithme looks like
 
154
    
 
155
    combo([4,5,8,12,9]) is :     _combo(4,X) for every X in combo([5,8,12,9])
 
156
                                                       +                     
 
157
                                 _combo(5,Y) for every Y in combo([4,8,12,9])
 
158
                                                       +                     
 
159
                                 _combo(8,Z) for every Z in combo([4,5,12,9])
 
160
                                                       +                     
 
161
                                 _combo(12,W) for every W in combo([4,5,8,9])
 
162
                                                       +                     
 
163
                                 _combo(9,V) for every V in combo([4,8,5,12])
 
164
 
 
165
    You can figure out from this demonstration that the total number of combinations
 
166
    for a stack of n numbers, for n > 2 is : 
 
167
    F(2) = 6           
 
168
    F(3) = 6*(F(2))*3  
 
169
    F(4) = 6*(F(3))*4  
 
170
    ...
 
171
    F(n) = 6*(F(n-1))*n
 
172
 
 
173
    (Is this is a geometrical serie ?)
 
174
 
 
175
    Now you'll understand why we don't put the results in a list before returning them :
 
176
    For 3 numbers, the number of possibilities is 108.
 
177
    For 4 numbers, 2.592.
 
178
    5 -> 77.760
 
179
    6 -> 2.799.360
 
180
    7 -> 117.573.120. That's a lot of memory :
 
181
 
 
182
    Each character is one byte and for 7 numbers you may have expressions like (5+(3*(8+2))/((4-2)*6)
 
183
    which are 22 characters long.
 
184
 
 
185
    22 characters are 22 bytes, which multiplies 117.573.120 is 2,586,608,640.
 
186
    That's approximatively 2.5 Gb of RAM, and that's why I got a memory error when I tried the
 
187
    list version of combo. So I rewrote it in a generative way (combo is a generator).
 
188
 
 
189
    The code to do this is 11 lines :
 
190
    """
 
191
 
 
192
    if len(S) == 2: # If there's only two numbers remaining in the stack
 
193
        for c in _combo(S[0],S[1]):
 
194
            yield ("("+c+")")
 
195
        return
 
196
    
 
197
    original = list(S)
 
198
    
 
199
    for e in original:
 
200
        S.remove(e)
 
201
        # don't throw away the yields ! use the generator
 
202
        #s = combo(S)
 
203
        for es in combo(S) :
 
204
            for c in _combo(e,es):
 
205
                yield ("("+c+")")
 
206
        S.append(e)
 
207
 
 
208
def _combo(a,b):
 
209
    """
 
210
    a and b mustn't be lists
 
211
    """
 
212
    L = []
 
213
    L.append(a+"+"+b)
 
214
    L.append(a+"-"+b)
 
215
    L.append(a+"*"+b)
 
216
    L.append(a+"/"+b)
 
217
    
 
218
    L.append(b+"/"+a)
 
219
    L.append(b+"-"+a)
 
220
    #L.append( b+"+"+a) # addition and multiplication are abelian,
 
221
    #L.append( b+"*"+a) # no need to repeat them
 
222
    return L    
 
223
 
 
224
def test5():
 
225
    import sys
 
226
    from number_pprint import number_pprint
 
227
    L = sys.argv[1:]
 
228
    i = 0
 
229
    for c in combo(L):
 
230
        print c
 
231
        i+=1
 
232
    print number_pprint(i),"possibilities for",len(L),"numbers"
 
233
        
 
234
if __name__ == "__main__":
 
235
    test5()