1
""" Change index / Reorder / Reverse order of limits of Sums and Products"""
2
from sympy.concrete import Product, Sum
6
class ReorderError(NotImplementedError):
8
Exception raised when trying to reorder dependent limits.
10
def __init__(self, expr, msg):
11
super(ReorderError, self).__init__(
12
"%s could not be reordered: %s." % (expr, msg))
17
Return the index of a limit variable.
22
``index(expr, x)`` returns the index of the limit variable ``x`` in the
23
limits of ``expr``. Note that we start counting with 0 at the inner-most
29
>>> from sympy.concrete.simplification import index
30
>>> from sympy.abc import x, y, a, b, c, d
31
>>> from sympy import Sum, Product
32
>>> index(Sum(x*y, (x, a, b), (y, c, d)), x)
34
>>> index(Sum(x*y, (x, a, b), (y, c, d)), y)
36
>>> index(Product(x*y, (x, a, b), (y, c, d)), x)
38
>>> index(Product(x*y, (x, a, b), (y, c, d)), y)
44
sympy.concrete.simplification.change_index,
45
sympy.concrete.simplification.reorder_limit,
46
sympy.concrete.simplification.reorder,
47
sympy.concrete.simplification.reverse_order
49
if isinstance(expr, Sum) or isinstance(expr, Product):
50
variables = [limit[0] for limit in expr.limits]
52
if variables.count(x) != 1:
53
raise ValueError(expr, "Number of instances of variable not equal to one")
55
return variables.index(x)
58
def change_index(expr, var, trafo, newvar=None):
60
Change index of a Sum or Product.
62
Perform a linear transformation `x \mapsto a x + b` on the index variable
63
`x`. For `a` the only values allowed are `\pm 1`. A new variable to be used
64
after the change of index can also be specified.
69
``change_index(expr, var, trafo, newvar=None)`` where ``var`` specifies the
70
index variable `x` to transform. The transformation ``trafo`` must be linear
71
and given in terms of ``var``. If the optional argument ``newvar`` is
72
provided then ``var`` gets replaced by ``newvar`` in the final expression.
77
>>> from sympy.concrete.simplification import change_index
78
>>> from sympy import Sum, Product, simplify
79
>>> from sympy.abc import x, y, a, b, c, d, u, v, i, j, k, l
81
>>> S = Sum(x, (x, a, b))
83
-a**2/2 + a/2 + b**2/2 + b/2
85
>>> Sn = change_index(S, x, x + 1, y)
87
Sum(y - 1, (y, a + 1, b + 1))
89
-a**2/2 + a/2 + b**2/2 + b/2
91
>>> Sn = change_index(S, x, -x, y)
95
-a**2/2 + a/2 + b**2/2 + b/2
97
>>> Sn = change_index(S, x, x+u)
99
Sum(-u + x, (x, a + u, b + u))
101
-a**2/2 - a*u + a/2 + b**2/2 + b*u + b/2 - u*(-a + b + 1) + u
102
>>> simplify(Sn.doit())
103
-a**2/2 + a/2 + b**2/2 + b/2
105
>>> Sn = change_index(S, x, -x - u, y)
107
Sum(-u - y, (y, -b - u, -a - u))
109
-a**2/2 - a*u + a/2 + b**2/2 + b*u + b/2 - u*(-a + b + 1) + u
110
>>> simplify(Sn.doit())
111
-a**2/2 + a/2 + b**2/2 + b/2
113
>>> P = Product(i*j**2, (i, a, b), (j, c, d))
115
Product(i*j**2, (i, a, b), (j, c, d))
116
>>> P2 = change_index(P, i, i+3, k)
118
Product(j**2*(k - 3), (k, a + 3, b + 3), (j, c, d))
119
>>> P3 = change_index(P2, j, -j, l)
121
Product(l**2*(k - 3), (k, a + 3, b + 3), (l, -d, -c))
123
When dealing with symbols only, we can make a
124
general linear transformation:
126
>>> Sn = change_index(S, x, u*x+v, y)
128
Sum((-v + y)/u, (y, b*u + v, a*u + v))
130
-v*(a*u - b*u + 1)/u + (a**2*u**2/2 + a*u*v + a*u/2 - b**2*u**2/2 - b*u*v + b*u/2 + v)/u
131
>>> simplify(Sn.doit())
132
a**2*u/2 + a/2 - b**2*u/2 + b/2
134
However, the last result can be inconsistent with usual
135
summation where the index increment is always 1. This is
136
obvious as we get back the original value only for ``u``
142
sympy.concrete.simplification.index,
143
sympy.concrete.simplification.reorder_limit,
144
sympy.concrete.simplification.reorder,
145
sympy.concrete.simplification.reverse_order
151
for limit in expr.limits:
153
p = trafo.as_poly(var)
155
raise ValueError("Index transformation is not linear")
156
alpha = p.coeff_monomial(var)
157
beta = p.coeff_monomial(S.One)
160
limits.append((newvar, alpha*limit[1] + beta, alpha*limit[2] + beta))
161
elif alpha == S.NegativeOne:
162
limits.append((newvar, alpha*limit[2] + beta, alpha*limit[1] + beta))
164
raise ValueError("Linear transformation results in non-linear summation stepsize")
166
# Note that the case of alpha being symbolic can give issues if alpha < 0.
167
limits.append((newvar, alpha*limit[2] + beta, alpha*limit[1] + beta))
171
function = expr.function.subs(var, (var - beta)/alpha)
172
function = function.subs(var, newvar)
174
if isinstance(expr, Sum):
175
return Sum(function, *tuple(limits))
176
elif isinstance(expr, Product):
177
return Product(function, *tuple(limits))
179
raise NotImplementedError(expr, "change_index only implemented for Sum and Product")
182
def reorder(expr, *arg):
184
Reorder limits in a expression containing a Sum or a Product.
189
``reorder(expr, *arg)`` reorders the limits in the expression ``expr``
190
according to the list of tuples given by ``arg``. These tuples can
191
contain numerical indices or index variable names or involve both.
196
>>> from sympy.concrete.simplification import reorder
197
>>> from sympy import Sum, Product
198
>>> from sympy.abc import x, y, z, a, b, c, d, e, f
200
>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (x, y))
201
Sum(x*y, (y, c, d), (x, a, b))
203
>>> reorder(Sum(x*y*z, (x, a, b), (y, c, d), (z, e, f)), (x, y), (x, z), (y, z))
204
Sum(x*y*z, (z, e, f), (y, c, d), (x, a, b))
206
>>> P = Product(x*y*z, (x, a, b), (y, c, d), (z, e, f))
207
>>> reorder(P, (x, y), (x, z), (y, z))
208
Product(x*y*z, (z, e, f), (y, c, d), (x, a, b))
210
We can also select the index variables by counting them, starting
211
with the inner-most one:
213
>>> reorder(Sum(x**2, (x, a, b), (x, c, d)), (0, 1))
214
Sum(x**2, (x, c, d), (x, a, b))
216
And of course we can mix both schemes:
218
>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (y, x))
219
Sum(x*y, (y, c, d), (x, a, b))
220
>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (y, 0))
221
Sum(x*y, (y, c, d), (x, a, b))
226
sympy.concrete.simplification.index,
227
sympy.concrete.simplification.change_index,
228
sympy.concrete.simplification.reorder_limit,
229
sympy.concrete.simplification.reverse_order
235
raise ValueError(r, "Invalid number of arguments")
240
if not isinstance(r[0], int):
241
index1 = index(expr, r[0])
242
if not isinstance(r[1], int):
243
index2 = index(expr, r[1])
245
new_expr = reorder_limit(new_expr, index1, index2)
250
def reorder_limit(expr, x, y):
252
Interchange two limit tuples of a Sum or Product expression.
257
``reorder_limit(expr, x, y)`` interchanges two limit tuples. The
258
arguments ``x`` and ``y`` are integers corresponding to the index
259
variables of the two limits which are to be interchanged. The
260
expression ``expr`` has to be either a Sum or a Product.
265
>>> from sympy.concrete.simplification import reorder_limit
266
>>> from sympy.abc import x, y, z, a, b, c, d, e, f
267
>>> from sympy import Sum, Product
269
>>> reorder_limit(Sum(x*y*z, (x, a, b), (y, c, d), (z, e, f)), 0, 2)
270
Sum(x*y*z, (z, e, f), (y, c, d), (x, a, b))
271
>>> reorder_limit(Sum(x**2, (x, a, b), (x, c, d)), 1, 0)
272
Sum(x**2, (x, c, d), (x, a, b))
274
>>> reorder_limit(Product(x*y*z, (x, a, b), (y, c, d), (z, e, f)), 0, 2)
275
Product(x*y*z, (z, e, f), (y, c, d), (x, a, b))
280
sympy.concrete.simplification.index,
281
sympy.concrete.simplification.change_index,
282
sympy.concrete.simplification.reorder,
283
sympy.concrete.simplification.reverse_order
285
var = set([limit[0] for limit in expr.limits])
286
limit_x = expr.limits[x]
287
limit_y = expr.limits[y]
289
if (len(set(limit_x[1].free_symbols).intersection(var)) == 0 and
290
len(set(limit_x[2].free_symbols).intersection(var)) == 0 and
291
len(set(limit_y[1].free_symbols).intersection(var)) == 0 and
292
len(set(limit_y[2].free_symbols).intersection(var)) == 0):
295
for i, limit in enumerate(expr.limits):
297
limits.append(limit_y)
299
limits.append(limit_x)
303
if isinstance(expr, Sum):
304
return Sum(expr.function, *limits)
305
elif isinstance(expr, Product):
306
return Product(expr.function, *limits)
308
raise NotImplementedError(expr, "reorder only implemented for Sum and Product")
311
raise ReorderError(expr, "could not interchange the two limits specified")
314
def reverse_order(expr, *indices):
316
Reverse the order of a limit in a Sum or Product.
321
``reverse_order(expr, *indices)`` reverses some limits in the expression
322
``expr`` which can be either a ``Sum`` or a ``Product``. The selectors in
323
the argument ``indices`` specify some indices whose limits get reversed.
324
These selectors are either variable names or numerical indices counted
325
starting from the inner-most limit tuple.
330
>>> from sympy.concrete.simplification import reverse_order
331
>>> from sympy import Sum
332
>>> from sympy.abc import x, y, a, b, c, d
334
>>> reverse_order(Sum(x, (x, 0, 3)), x)
336
>>> reverse_order(Sum(x*y, (x, 1, 5), (y, 0, 6)), x, y)
337
Sum(x*y, (x, 6, 0), (y, 7, -1))
338
>>> reverse_order(Sum(x, (x, a, b)), x)
339
Sum(-x, (x, b + 1, a - 1))
340
>>> reverse_order(Sum(x, (x, a, b)), 0)
341
Sum(-x, (x, b + 1, a - 1))
343
>>> from sympy import Product, simplify, RisingFactorial, gamma
344
>>> P = Product(x, (x, a, b))
345
>>> Pr = reverse_order(P, x)
347
Product(1/x, (x, b + 1, a - 1))
350
1/RisingFactorial(b + 1, a - b - 1)
352
gamma(b + 1)/gamma(a)
355
RisingFactorial(a, -a + b + 1)
357
gamma(b + 1)/gamma(a)
359
While one should prefer variable names when specifying which limits
360
to reverse, the index counting notation comes in handy in case there
361
are several symbols with the same name.
363
>>> S = Sum(x**2, (x, a, b), (x, c, d))
365
Sum(x**2, (x, a, b), (x, c, d))
366
>>> S0 = reverse_order(S, 0)
368
Sum(-x**2, (x, b + 1, a - 1), (x, c, d))
369
>>> S1 = reverse_order(S0, 1)
371
Sum(x**2, (x, b + 1, a - 1), (x, d + 1, c - 1))
373
Of course we can mix both notations:
375
>>> reverse_order(Sum(x*y, (x, a, b), (y, 2, 5)), x, 1)
376
Sum(x*y, (x, b + 1, a - 1), (y, 6, 1))
377
>>> reverse_order(Sum(x*y, (x, a, b), (y, 2, 5)), y, x)
378
Sum(x*y, (x, b + 1, a - 1), (y, 6, 1))
383
sympy.concrete.simplification.index,
384
sympy.concrete.simplification.change_index,
385
sympy.concrete.simplification.reorder_limit,
386
sympy.concrete.simplification.reorder
391
.. [1] Michael Karr, "Summation in Finite Terms", Journal of the ACM,
392
Volume 28 Issue 2, April 1981, Pages 305-350
393
http://dl.acm.org/citation.cfm?doid=322248.322255
395
l_indices = list(indices)
397
for i, indx in enumerate(l_indices):
398
if not isinstance(indx, int):
399
l_indices[i] = index(expr, indx)
401
if isinstance(expr, Sum) or isinstance(expr, Product):
404
for i, limit in enumerate(expr.limits):
408
l = (limit[0], limit[2] + 1 , limit[1] - 1)
411
if isinstance(expr, Sum):
412
return Sum(e * expr.function, *limits)
413
elif isinstance(expr, Product):
414
return Product(expr.function ** e, *limits)