10 Hash of a sequence, that *depends* on the order of elements.
12 # make this more robust:
15 m
= hash(m
+ 1001 ^
hash(x
))
18 def compare_lists(a
, b
):
20 Compare two sequences.
22 Sequences are equal even with a *different* order of elements.
25 return set(a
) == set(b
)
29 def __new__(cls
, type, args
):
30 obj
= object.__new
__(cls
)
32 obj
._args
= tuple(args
)
39 return hash_seq(self
.args
)
45 def as_coeff_rest(self
):
46 return (Integer(1), self
)
48 def as_base_exp(self
):
49 return (self
, Integer(1))
73 return Mul((x
, Pow((y
, Integer(-1)))))
76 return Mul((y
, Pow((x
, Integer(-1)))))
85 return Mul((Integer(-1), x
))
91 return not self
.__eq
__(x
)
95 if o
.type == self
.type:
96 return self
.args
== o
.args
101 class Integer(Basic
):
104 obj
= Basic
.__new
__(cls
, INTEGER
, [])
113 if o
.type == INTEGER
:
121 def __add__(self
, o
):
123 if o
.type == INTEGER
:
124 return Integer(self
.i
+o
.i
)
125 return Basic
.__add
__(self
, o
)
127 def __mul__(self
, o
):
129 if o
.type == INTEGER
:
130 return Integer(self
.i
*o
.i
)
131 return Basic
.__mul
__(self
, o
)
136 def __new__(cls
, name
):
137 obj
= Basic
.__new
__(cls
, SYMBOL
, [])
142 return hash(self
.name
)
147 return self
.name
== o
.name
156 def __new__(cls
, args
, canonicalize
=True):
157 if canonicalize
== False:
158 obj
= Basic
.__new
__(cls
, ADD
, args
)
160 args
= [sympify(x
) for x
in args
]
161 return Add
.canonicalize(args
)
164 def canonicalize(cls
, args
):
168 if a
.type == INTEGER
:
172 if b
.type == INTEGER
:
175 coeff
, key
= b
.as_coeff_rest()
181 coeff
, key
= a
.as_coeff_rest()
190 for a
, b
in d
.iteritems():
191 args
.append(Mul((a
, b
)))
197 return Add(args
, False)
202 return compare_lists(self
.args
, o
.args
)
207 s
= str(self
.args
[0])
208 if self
.args
[0].type == ADD
:
210 for x
in self
.args
[1:]:
211 s
= "%s + %s" % (s
, str(x
))
217 a
= list(self
.args
[:])
220 return hash(frozenset(self
.args
))
224 for term
in self
.args
:
230 def __new__(cls
, args
, canonicalize
=True):
231 if canonicalize
== False:
232 obj
= Basic
.__new
__(cls
, MUL
, args
)
234 args
= [sympify(x
) for x
in args
]
235 return Mul
.canonicalize(args
)
238 def canonicalize(cls
, args
):
241 from csympy
import HashTable
247 if a
.type == INTEGER
:
251 if b
.type == INTEGER
:
254 key
, coeff
= b
.as_base_exp()
260 key
, coeff
= a
.as_base_exp()
265 if num
.i
== 0 or len(d
)==0:
268 for a
, b
in d
.iteritems():
269 args
.append(Pow((a
, b
)))
275 return Mul(args
, False)
278 a
= list(self
.args
[:])
281 return hash(frozenset(self
.args
))
286 return compare_lists(self
.args
, o
.args
)
291 def as_coeff_rest(self
):
292 if self
.args
[0].type == INTEGER
:
293 return self
.as_two_terms()
294 return (Integer(1), self
)
296 def as_two_terms(self
):
297 return (self
.args
[0], Mul(self
.args
[1:]))
301 s
= str(self
.args
[0])
302 if self
.args
[0].type in [ADD
, MUL
]:
304 for x
in self
.args
[1:]:
305 if x
.type in [ADD
, MUL
]:
306 s
= "%s * (%s)" % (s
, str(x
))
308 s
= "%s*%s" % (s
, str(x
))
312 def expand_two(self
, a
, b
):
314 Both a and b are assumed to be expanded.
316 if a
.type == ADD
and b
.type == ADD
:
335 a
, b
= self
.as_two_terms()
338 return Mul
.expand_two(a
, b
)
342 def __new__(cls
, args
, canonicalize
=True):
343 if canonicalize
== False:
344 obj
= Basic
.__new
__(cls
, POW
, args
)
346 args
= [sympify(x
) for x
in args
]
347 return Pow
.canonicalize(args
)
350 def canonicalize(cls
, args
):
352 if base
.type == INTEGER
:
357 if exp
.type == INTEGER
:
363 return Pow((base
.args
[0], base
.args
[1]*exp
))
364 return Pow(args
, False)
367 s
= str(self
.args
[0])
368 if self
.args
[0].type == ADD
:
370 if self
.args
[1].type == ADD
:
371 s
= "%s^(%s)" % (s
, str(self
.args
[1]))
373 s
= "%s^%s" % (s
, str(self
.args
[1]))
376 def as_base_exp(self
):
380 base
, exp
= self
.args
381 if base
.type == ADD
and exp
.type == INTEGER
:
384 d
= multinomial_coefficients(m
, n
)
386 for powers
, coeff
in d
.iteritems():
388 for x
, p
in zip(base
.args
, powers
):
395 if isinstance(x
, int):
401 Create a symbolic variable with the name *s*.
404 s -- a string, either a single variable name, or
405 a space separated list of variable names, or
406 a list of variable names.
408 NOTE: The new variable is both returned and automatically injected into
409 the parent's *global* namespace. It's recommended not to use "var" in
410 library code, it is better to use symbols() instead.
413 We define some symbolic variables:
416 >>> var('n xx yy zz')
424 frame
= inspect
.currentframe().f_back
427 if not isinstance(s
, list):
428 s
= re
.split('\s|,', s
)
437 frame
.f_globals
[t
] = sym
441 if len(res
) == 0: # var('')
443 elif len(res
) == 1: # var('x')
445 # otherwise var('a b ...')
449 # we should explicitly break cyclic dependencies as stated in inspect
453 def binomial_coefficients(n
):
454 """Return a dictionary containing pairs {(k1,k2) : C_kn} where
455 C_kn are binomial coefficients and n=k1+k2."""
456 d
= {(0, n
):1, (n
, 0):1}
458 for k
in xrange(1, n
//2+1):
460 d
[k
, n
-k
] = d
[n
-k
, k
] = a
463 def binomial_coefficients_list(n
):
464 """ Return a list of binomial coefficients as rows of the Pascal's
469 for k
in xrange(1, n
//2+1):
474 def multinomial_coefficients(m
, n
, _tuple
=tuple, _zip
=zip):
475 """Return a dictionary containing pairs ``{(k1,k2,..,km) : C_kn}``
476 where ``C_kn`` are multinomial coefficients such that
481 >>> print multinomial_coefficients(2,5)
482 {(3, 2): 10, (1, 4): 5, (2, 3): 10, (5, 0): 1, (0, 5): 1, (4, 1): 5}
484 The algorithm is based on the following result:
486 Consider a polynomial and it's ``m``-th exponent::
488 P(x) = sum_{i=0}^m p_i x^k
489 P(x)^n = sum_{k=0}^{m n} a(n,k) x^k
491 The coefficients ``a(n,k)`` can be computed using the
492 J.C.P. Miller Pure Recurrence [see D.E.Knuth, Seminumerical
493 Algorithms, The art of Computer Programming v.2, Addison
494 Wesley, Reading, 1981;]::
496 a(n,k) = 1/(k p_0) sum_{i=1}^m p_i ((n+1)i-k) a(n,k-i),
498 where ``a(n,0) = p_0^n``.
502 return binomial_coefficients(n
)
503 symbols
= [(0,)*i
+ (1,) + (0,)*(m
-i
-1) for i
in range(m
)]
505 p0
= [_tuple(aa
-bb
for aa
,bb
in _zip(s
,s0
)) for s
in symbols
]
506 r
= {_tuple(aa
*n
for aa
in s0
):1}
509 l
= [0] * (n
*(m
-1)+1)
511 for k
in xrange(1, n
*(m
-1)+1):
514 for i
in xrange(1, min(m
,k
+1)):
519 for t2
, c2
in l
[k
-i
]:
520 tt
= _tuple([aa
+bb
for aa
,bb
in _zip(t2
,t
)])
531 r1
= [(t
, c
//k
) for (t
, c
) in d
.iteritems()]