10 Hash of a sequence, that *depends* on the order of elements.
12 # make this more robust:
15 m
= hash(m
+ 1001 ^
hash(x
))
20 def __new__(cls
, type, args
):
21 obj
= object.__new
__(cls
)
23 obj
._args
= tuple(args
)
31 if self
.mhash
is None:
32 h
= hash_seq(self
.args
)
42 def as_coeff_rest(self
):
43 return (Integer(1), self
)
45 def as_base_exp(self
):
46 return (self
, Integer(1))
70 return Mul((x
, Pow((y
, Integer(-1)))))
73 return Mul((y
, Pow((x
, Integer(-1)))))
82 return Mul((Integer(-1), x
))
88 return not self
.__eq
__(x
)
92 if o
.type == self
.type:
93 return self
.args
== o
.args
101 obj
= Basic
.__new
__(cls
, INTEGER
, [])
106 if self
.mhash
is None:
115 if o
.type == INTEGER
:
123 def __add__(self
, o
):
125 if o
.type == INTEGER
:
126 return Integer(self
.i
+o
.i
)
127 return Basic
.__add
__(self
, o
)
129 def __mul__(self
, o
):
131 if o
.type == INTEGER
:
132 return Integer(self
.i
*o
.i
)
133 return Basic
.__mul
__(self
, o
)
138 def __new__(cls
, name
):
139 obj
= Basic
.__new
__(cls
, SYMBOL
, [])
144 if self
.mhash
is None:
154 return self
.name
== o
.name
163 def __new__(cls
, args
, canonicalize
=True):
164 if canonicalize
== False:
165 obj
= Basic
.__new
__(cls
, ADD
, args
)
168 args
= [sympify(x
) for x
in args
]
169 return Add
.canonicalize(args
)
172 def canonicalize(cls
, args
):
175 from csympy
import HashTable
181 if a
.type == INTEGER
:
185 if b
.type == INTEGER
:
188 coeff
, key
= b
.as_coeff_rest()
194 coeff
, key
= a
.as_coeff_rest()
202 for a
, b
in d
.iteritems():
203 args
.append(Mul((a
, b
)))
209 return Add(args
, False)
211 def freeze_args(self
):
212 #print "add is freezing"
213 if self
._args
_set
is None:
214 self
._args
_set
= frozenset(self
.args
)
222 return self
._args
_set
== o
._args
_set
227 s
= str(self
.args
[0])
228 if self
.args
[0].type == ADD
:
230 for x
in self
.args
[1:]:
231 s
= "%s + %s" % (s
, str(x
))
237 if self
.mhash
is None:
238 # XXX: it is surprising, but this is *not* faster:
240 #h = hash(self._args_set)
243 a
= list(self
.args
[:])
253 for term
in self
.args
:
259 def __new__(cls
, args
, canonicalize
=True):
260 if canonicalize
== False:
261 obj
= Basic
.__new
__(cls
, MUL
, args
)
264 args
= [sympify(x
) for x
in args
]
265 return Mul
.canonicalize(args
)
268 def canonicalize(cls
, args
):
271 from csympy
import HashTable
277 if a
.type == INTEGER
:
281 if b
.type == INTEGER
:
284 key
, coeff
= b
.as_base_exp()
290 key
, coeff
= a
.as_base_exp()
295 if num
.i
== 0 or len(d
)==0:
298 for a
, b
in d
.iteritems():
299 args
.append(Pow((a
, b
)))
305 return Mul(args
, False)
308 if self
.mhash
is None:
309 # in contrast to Add, here it is faster:
311 h
= hash(self
._args
_set
)
313 #a = list(self.args[:])
321 def freeze_args(self
):
322 #print "mul is freezing"
323 if self
._args
_set
is None:
324 self
._args
_set
= frozenset(self
.args
)
332 return self
._args
_set
== o
._args
_set
337 def as_coeff_rest(self
):
338 if self
.args
[0].type == INTEGER
:
339 return self
.as_two_terms()
340 return (Integer(1), self
)
342 def as_two_terms(self
):
343 return (self
.args
[0], Mul(self
.args
[1:]))
347 s
= str(self
.args
[0])
348 if self
.args
[0].type in [ADD
, MUL
]:
350 for x
in self
.args
[1:]:
351 if x
.type in [ADD
, MUL
]:
352 s
= "%s * (%s)" % (s
, str(x
))
354 s
= "%s*%s" % (s
, str(x
))
358 def expand_two(self
, a
, b
):
360 Both a and b are assumed to be expanded.
362 if a
.type == ADD
and b
.type == ADD
:
381 a
, b
= self
.as_two_terms()
382 r
= Mul
.expand_two(a
, b
)
386 return Mul
.expand_two(a
, b
)
392 def __new__(cls
, args
, canonicalize
=True):
393 if canonicalize
== False:
394 obj
= Basic
.__new
__(cls
, POW
, args
)
396 args
= [sympify(x
) for x
in args
]
397 return Pow
.canonicalize(args
)
400 def canonicalize(cls
, args
):
402 if base
.type == INTEGER
:
407 if exp
.type == INTEGER
:
413 return Pow((base
.args
[0], base
.args
[1]*exp
))
414 return Pow(args
, False)
417 s
= str(self
.args
[0])
418 if self
.args
[0].type == ADD
:
420 if self
.args
[1].type == ADD
:
421 s
= "%s^(%s)" % (s
, str(self
.args
[1]))
423 s
= "%s^%s" % (s
, str(self
.args
[1]))
426 def as_base_exp(self
):
430 base
, exp
= self
.args
431 if base
.type == ADD
and exp
.type == INTEGER
:
435 d
= multinomial_coefficients(m
, n
)
438 for powers
, coeff
in d
.iteritems():
443 for x
, p
in zip(base
.args
, powers
):
445 t
.append(Pow((x
, p
)))
458 if isinstance(x
, int):
464 Create a symbolic variable with the name *s*.
467 s -- a string, either a single variable name, or
468 a space separated list of variable names, or
469 a list of variable names.
471 NOTE: The new variable is both returned and automatically injected into
472 the parent's *global* namespace. It's recommended not to use "var" in
473 library code, it is better to use symbols() instead.
476 We define some symbolic variables:
479 >>> var('n xx yy zz')
487 frame
= inspect
.currentframe().f_back
490 if not isinstance(s
, list):
491 s
= re
.split('\s|,', s
)
500 frame
.f_globals
[t
] = sym
504 if len(res
) == 0: # var('')
506 elif len(res
) == 1: # var('x')
508 # otherwise var('a b ...')
512 # we should explicitly break cyclic dependencies as stated in inspect
516 def binomial_coefficients(n
):
517 """Return a dictionary containing pairs {(k1,k2) : C_kn} where
518 C_kn are binomial coefficients and n=k1+k2."""
519 d
= {(0, n
):1, (n
, 0):1}
521 for k
in xrange(1, n
//2+1):
523 d
[k
, n
-k
] = d
[n
-k
, k
] = a
526 def binomial_coefficients_list(n
):
527 """ Return a list of binomial coefficients as rows of the Pascal's
532 for k
in xrange(1, n
//2+1):
537 def multinomial_coefficients(m
, n
, _tuple
=tuple, _zip
=zip):
538 """Return a dictionary containing pairs ``{(k1,k2,..,km) : C_kn}``
539 where ``C_kn`` are multinomial coefficients such that
544 >>> print multinomial_coefficients(2,5)
545 {(3, 2): 10, (1, 4): 5, (2, 3): 10, (5, 0): 1, (0, 5): 1, (4, 1): 5}
547 The algorithm is based on the following result:
549 Consider a polynomial and it's ``m``-th exponent::
551 P(x) = sum_{i=0}^m p_i x^k
552 P(x)^n = sum_{k=0}^{m n} a(n,k) x^k
554 The coefficients ``a(n,k)`` can be computed using the
555 J.C.P. Miller Pure Recurrence [see D.E.Knuth, Seminumerical
556 Algorithms, The art of Computer Programming v.2, Addison
557 Wesley, Reading, 1981;]::
559 a(n,k) = 1/(k p_0) sum_{i=1}^m p_i ((n+1)i-k) a(n,k-i),
561 where ``a(n,0) = p_0^n``.
565 return binomial_coefficients(n
)
566 symbols
= [(0,)*i
+ (1,) + (0,)*(m
-i
-1) for i
in range(m
)]
568 p0
= [_tuple(aa
-bb
for aa
,bb
in _zip(s
,s0
)) for s
in symbols
]
569 r
= {_tuple(aa
*n
for aa
in s0
):1}
572 l
= [0] * (n
*(m
-1)+1)
574 for k
in xrange(1, n
*(m
-1)+1):
577 for i
in xrange(1, min(m
,k
+1)):
582 for t2
, c2
in l
[k
-i
]:
583 tt
= _tuple([aa
+bb
for aa
,bb
in _zip(t2
,t
)])
594 r1
= [(t
, c
//k
) for (t
, c
) in d
.iteritems()]