# Source code for sympy.concrete.simplification

""" Change index / Reorder / Reverse order of limits of Sums and Products"""
from sympy.concrete import Product, Sum
from sympy import S

class ReorderError(NotImplementedError):
"""
Exception raised when trying to reorder dependent limits.
"""
def __init__(self, expr, msg):
super(ReorderError, self).__init__(
"%s could not be reordered: %s." % (expr, msg))

[docs]def index(expr, x):
"""
Return the index of a limit variable.

Usage
=====

index(expr, x)  returns the index of the limit variable x in the
limits of expr. Note that we start counting with 0 at the inner-most
limits tuple.

Examples
========

>>> from sympy.concrete.simplification import index
>>> from sympy.abc import x, y, a, b, c, d
>>> from sympy import Sum, Product
>>> index(Sum(x*y, (x, a, b), (y, c, d)), x)
0
>>> index(Sum(x*y, (x, a, b), (y, c, d)), y)
1
>>> index(Product(x*y, (x, a, b), (y, c, d)), x)
0
>>> index(Product(x*y, (x, a, b), (y, c, d)), y)
1

========

sympy.concrete.simplification.change_index,
sympy.concrete.simplification.reorder_limit,
sympy.concrete.simplification.reorder,
sympy.concrete.simplification.reverse_order
"""
if isinstance(expr, Sum) or isinstance(expr, Product):
variables = [limit[0] for limit in expr.limits]

if variables.count(x) != 1:
raise ValueError(expr, "Number of instances of variable not equal to one")
else:
return variables.index(x)

[docs]def change_index(expr, var, trafo, newvar=None):
"""
Change index of a Sum or Product.

Perform a linear transformation x \mapsto a x + b on the index variable
x. For a the only values allowed are \pm 1. A new variable to be used
after the change of index can also be specified.

Usage
=====

change_index(expr, var, trafo, newvar=None) where var specifies the
index variable x to transform. The transformation trafo must be linear
and given in terms of var. If the optional argument newvar is
provided then var gets replaced by newvar in the final expression.

Examples
========

>>> from sympy.concrete.simplification import change_index
>>> from sympy import Sum, Product, simplify
>>> from sympy.abc import x, y, a, b, c, d, u, v, i, j, k, l

>>> S = Sum(x, (x, a, b))
>>> S.doit()
-a**2/2 + a/2 + b**2/2 + b/2

>>> Sn = change_index(S, x, x + 1, y)
>>> Sn
Sum(y - 1, (y, a + 1, b + 1))
>>> Sn.doit()
-a**2/2 + a/2 + b**2/2 + b/2

>>> Sn = change_index(S, x, -x, y)
>>> Sn
Sum(-y, (y, -b, -a))
>>> Sn.doit()
-a**2/2 + a/2 + b**2/2 + b/2

>>> Sn = change_index(S, x, x+u)
>>> Sn
Sum(-u + x, (x, a + u, b + u))
>>> Sn.doit()
-a**2/2 - a*u + a/2 + b**2/2 + b*u + b/2 - u*(-a + b + 1) + u
>>> simplify(Sn.doit())
-a**2/2 + a/2 + b**2/2 + b/2

>>> Sn = change_index(S, x, -x - u, y)
>>> Sn
Sum(-u - y, (y, -b - u, -a - u))
>>> Sn.doit()
-a**2/2 - a*u + a/2 + b**2/2 + b*u + b/2 - u*(-a + b + 1) + u
>>> simplify(Sn.doit())
-a**2/2 + a/2 + b**2/2 + b/2

>>> P = Product(i*j**2, (i, a, b), (j, c, d))
>>> P
Product(i*j**2, (i, a, b), (j, c, d))
>>> P2 = change_index(P, i, i+3, k)
>>> P2
Product(j**2*(k - 3), (k, a + 3, b + 3), (j, c, d))
>>> P3 = change_index(P2, j, -j, l)
>>> P3
Product(l**2*(k - 3), (k, a + 3, b + 3), (l, -d, -c))

When dealing with symbols only, we can make a
general linear transformation:

>>> Sn = change_index(S, x, u*x+v, y)
>>> Sn
Sum((-v + y)/u, (y, b*u + v, a*u + v))
>>> Sn.doit()
-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
>>> simplify(Sn.doit())
a**2*u/2 + a/2 - b**2*u/2 + b/2

However, the last result can be inconsistent with usual
summation where the index increment is always 1. This is
obvious as we get back the original value only for u
equal +1 or -1.

========

sympy.concrete.simplification.index,
sympy.concrete.simplification.reorder_limit,
sympy.concrete.simplification.reorder,
sympy.concrete.simplification.reverse_order
"""
if newvar is None:
newvar = var

limits = []
for limit in expr.limits:
if limit[0] == var:
p = trafo.as_poly(var)
if p.degree() != 1:
raise ValueError("Index transformation is not linear")
alpha = p.coeff_monomial(var)
beta = p.coeff_monomial(S.One)
if alpha.is_number:
if alpha == S.One:
limits.append((newvar, alpha*limit[1] + beta, alpha*limit[2] + beta))
elif alpha == S.NegativeOne:
limits.append((newvar, alpha*limit[2] + beta, alpha*limit[1] + beta))
else:
raise ValueError("Linear transformation results in non-linear summation stepsize")
else:
# Note that the case of alpha being symbolic can give issues if alpha < 0.
limits.append((newvar, alpha*limit[2] + beta, alpha*limit[1] + beta))
else:
limits.append(limit)

function = expr.function.subs(var, (var - beta)/alpha)
function = function.subs(var, newvar)

if isinstance(expr, Sum):
return Sum(function, *tuple(limits))
elif isinstance(expr, Product):
return Product(function, *tuple(limits))
else:
raise NotImplementedError(expr, "change_index only implemented for Sum and Product")

[docs]def reorder(expr, *arg):
"""
Reorder limits in a expression containing a Sum or a Product.

Usage
=====

reorder(expr, *arg) reorders the limits in the expression expr
according to the list of tuples given by arg. These tuples can
contain numerical indices or index variable names or involve both.

Examples
========

>>> from sympy.concrete.simplification import reorder
>>> from sympy import Sum, Product
>>> from sympy.abc import x, y, z, a, b, c, d, e, f

>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (x, y))
Sum(x*y, (y, c, d), (x, a, b))

>>> reorder(Sum(x*y*z, (x, a, b), (y, c, d), (z, e, f)), (x, y), (x, z), (y, z))
Sum(x*y*z, (z, e, f), (y, c, d), (x, a, b))

>>> P = Product(x*y*z, (x, a, b), (y, c, d), (z, e, f))
>>> reorder(P, (x, y), (x, z), (y, z))
Product(x*y*z, (z, e, f), (y, c, d), (x, a, b))

We can also select the index variables by counting them, starting
with the inner-most one:

>>> reorder(Sum(x**2, (x, a, b), (x, c, d)), (0, 1))
Sum(x**2, (x, c, d), (x, a, b))

And of course we can mix both schemes:

>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (y, x))
Sum(x*y, (y, c, d), (x, a, b))
>>> reorder(Sum(x*y, (x, a, b), (y, c, d)), (y, 0))
Sum(x*y, (y, c, d), (x, a, b))

========

sympy.concrete.simplification.index,
sympy.concrete.simplification.change_index,
sympy.concrete.simplification.reorder_limit,
sympy.concrete.simplification.reverse_order
"""
new_expr = expr

for r in arg:
if len(r) != 2:
raise ValueError(r, "Invalid number of arguments")

index1 = r[0]
index2 = r[1]

if not isinstance(r[0], int):
index1 = index(expr, r[0])
if not isinstance(r[1], int):
index2 = index(expr, r[1])

new_expr = reorder_limit(new_expr, index1, index2)

return new_expr

[docs]def reorder_limit(expr, x, y):
"""
Interchange two limit tuples of a Sum or Product expression.

Usage
=====

reorder_limit(expr, x, y) interchanges two limit tuples. The
arguments x and y are integers corresponding to the index
variables of the two limits which are to be interchanged. The
expression expr has to be either a Sum or a Product.

Examples
========

>>> from sympy.concrete.simplification import reorder_limit
>>> from sympy.abc import x, y, z, a, b, c, d, e, f
>>> from sympy import Sum, Product

>>> reorder_limit(Sum(x*y*z, (x, a, b), (y, c, d), (z, e, f)), 0, 2)
Sum(x*y*z, (z, e, f), (y, c, d), (x, a, b))
>>> reorder_limit(Sum(x**2, (x, a, b), (x, c, d)), 1, 0)
Sum(x**2, (x, c, d), (x, a, b))

>>> reorder_limit(Product(x*y*z, (x, a, b), (y, c, d), (z, e, f)), 0, 2)
Product(x*y*z, (z, e, f), (y, c, d), (x, a, b))

========

sympy.concrete.simplification.index,
sympy.concrete.simplification.change_index,
sympy.concrete.simplification.reorder,
sympy.concrete.simplification.reverse_order
"""
var = set([limit[0] for limit in expr.limits])
limit_x = expr.limits[x]
limit_y = expr.limits[y]

if (len(set(limit_x[1].free_symbols).intersection(var)) == 0 and
len(set(limit_x[2].free_symbols).intersection(var)) == 0 and
len(set(limit_y[1].free_symbols).intersection(var)) == 0 and
len(set(limit_y[2].free_symbols).intersection(var)) == 0):

limits = []
for i, limit in enumerate(expr.limits):
if i == x:
limits.append(limit_y)
elif i == y:
limits.append(limit_x)
else:
limits.append(limit)

if isinstance(expr, Sum):
return Sum(expr.function, *limits)
elif isinstance(expr, Product):
return Product(expr.function, *limits)
else:
raise NotImplementedError(expr, "reorder only implemented for Sum and Product")

else:
raise ReorderError(expr, "could not interchange the two limits specified")

[docs]def reverse_order(expr, *indices):
"""
Reverse the order of a limit in a Sum or Product.

Usage
=====

reverse_order(expr, *indices) reverses some limits in the expression
expr which can be either a Sum or a Product. The selectors in
the argument indices specify some indices whose limits get reversed.
These selectors are either variable names or numerical indices counted
starting from the inner-most limit tuple.

Examples
========

>>> from sympy.concrete.simplification import reverse_order
>>> from sympy import Sum
>>> from sympy.abc import x, y, a, b, c, d

>>> reverse_order(Sum(x, (x, 0, 3)), x)
Sum(-x, (x, 4, -1))
>>> reverse_order(Sum(x*y, (x, 1, 5), (y, 0, 6)), x, y)
Sum(x*y, (x, 6, 0), (y, 7, -1))
>>> reverse_order(Sum(x, (x, a, b)), x)
Sum(-x, (x, b + 1, a - 1))
>>> reverse_order(Sum(x, (x, a, b)), 0)
Sum(-x, (x, b + 1, a - 1))

>>> from sympy import Product, simplify, RisingFactorial, gamma
>>> P = Product(x, (x, a, b))
>>> Pr = reverse_order(P, x)
>>> Pr
Product(1/x, (x, b + 1, a - 1))
>>> Pr = Pr.doit()
>>> Pr
1/RisingFactorial(b + 1, a - b - 1)
>>> simplify(Pr)
gamma(b + 1)/gamma(a)
>>> P = P.doit()
>>> P
RisingFactorial(a, -a + b + 1)
>>> simplify(P)
gamma(b + 1)/gamma(a)

While one should prefer variable names when specifying which limits
to reverse, the index counting notation comes in handy in case there
are several symbols with the same name.

>>> S = Sum(x**2, (x, a, b), (x, c, d))
>>> S
Sum(x**2, (x, a, b), (x, c, d))
>>> S0 = reverse_order(S, 0)
>>> S0
Sum(-x**2, (x, b + 1, a - 1), (x, c, d))
>>> S1 = reverse_order(S0, 1)
>>> S1
Sum(x**2, (x, b + 1, a - 1), (x, d + 1, c - 1))

Of course we can mix both notations:

>>> reverse_order(Sum(x*y, (x, a, b), (y, 2, 5)), x, 1)
Sum(x*y, (x, b + 1, a - 1), (y, 6, 1))
>>> reverse_order(Sum(x*y, (x, a, b), (y, 2, 5)), y, x)
Sum(x*y, (x, b + 1, a - 1), (y, 6, 1))

========

sympy.concrete.simplification.index,
sympy.concrete.simplification.change_index,
sympy.concrete.simplification.reorder_limit,
sympy.concrete.simplification.reorder

References
==========

.. [1] Michael Karr, "Summation in Finite Terms", Journal of the ACM,
Volume 28 Issue 2, April 1981, Pages 305-350
http://dl.acm.org/citation.cfm?doid=322248.322255
"""
l_indices = list(indices)

for i, indx in enumerate(l_indices):
if not isinstance(indx, int):
l_indices[i] = index(expr, indx)

if isinstance(expr, Sum) or isinstance(expr, Product):
e = 1
limits = []
for i, limit in enumerate(expr.limits):
l = limit
if i in l_indices:
e = -e
l = (limit[0], limit[2] + 1 , limit[1] - 1)
limits.append(l)

if isinstance(expr, Sum):
return Sum(e * expr.function, *limits)
elif isinstance(expr, Product):
return Product(expr.function ** e, *limits)
else:
return expr