Coverage for sympy/sets/fancysets.py : 31%

from __future__ import print_function, division 

from sympy.logic.boolalg import And 

from sympy.core.add import Add 

from sympy.core.basic import Basic 

from sympy.core.compatibility import as_int, with_metaclass, range, PY3 

from sympy.core.expr import Expr 

from sympy.core.function import Lambda, _coeff_isneg 

from sympy.core.singleton import Singleton, S 

from sympy.core.symbol import Dummy, symbols, Wild 

from sympy.core.sympify import _sympify, sympify, converter 

from sympy.sets.sets import (Set, Interval, Intersection, EmptySet, Union, 

FiniteSet, imageset) 

from sympy.sets.conditionset import ConditionSet 

from sympy.utilities.misc import filldedent, func_name 

class Naturals(with_metaclass(Singleton, Set)): 

""" 

Represents the natural numbers (or counting numbers) which are all 

positive integers starting from 1. This set is also available as 

the Singleton, S.Naturals. 

Examples 

======== 

>>> from sympy import S, Interval, pprint 

>>> 5 in S.Naturals 

True 

>>> iterable = iter(S.Naturals) 

>>> next(iterable) 

1 

>>> next(iterable) 

2 

>>> next(iterable) 

3 

>>> pprint(S.Naturals.intersect(Interval(0, 10))) 

{1, 2, ..., 10} 

See Also 

======== 

Naturals0 : non-negative integers (i.e. includes 0, too) 

Integers : also includes negative integers 

""" 

is_iterable = True 

_inf = S.One 

_sup = S.Infinity 

def _intersect(self, other): 

if other.is_Interval: 

return Intersection( 

S.Integers, other, Interval(self._inf, S.Infinity)) 

return None 

def _contains(self, other): 

if other.is_positive and other.is_integer: 

return S.true 

elif other.is_integer is False or other.is_positive is False: 

return S.false 

def __iter__(self): 

i = self._inf 

while True: 

yield i 

i = i + 1 

@property 

def _boundary(self): 

return self 

class Naturals0(Naturals): 

"""Represents the whole numbers which are all the non-negative integers, 

inclusive of zero. 

See Also 

======== 

Naturals : positive integers; does not include 0 

Integers : also includes the negative integers 

""" 

_inf = S.Zero 

def _contains(self, other): 

if other.is_integer and other.is_nonnegative: 

return S.true 

elif other.is_integer is False or other.is_nonnegative is False: 

return S.false 

class Integers(with_metaclass(Singleton, Set)): 

""" 

Represents all integers: positive, negative and zero. This set is also 

available as the Singleton, S.Integers. 

Examples 

======== 

>>> from sympy import S, Interval, pprint 

>>> 5 in S.Naturals 

True 

>>> iterable = iter(S.Integers) 

>>> next(iterable) 

0 

>>> next(iterable) 

1 

>>> next(iterable) 

-1 

>>> next(iterable) 

2 

>>> pprint(S.Integers.intersect(Interval(-4, 4))) 

{-4, -3, ..., 4} 

See Also 

======== 

Naturals0 : non-negative integers 

Integers : positive and negative integers and zero 

""" 

is_iterable = True 

def _intersect(self, other): 

from sympy.functions.elementary.integers import floor, ceiling 

if other is Interval(S.NegativeInfinity, S.Infinity) or other is S.Reals: 

return self 

elif other.is_Interval: 

s = Range(ceiling(other.left), floor(other.right) + 1) 

return s.intersect(other) # take out endpoints if open interval 

return None 

def _contains(self, other): 

if other.is_integer: 

return S.true 

elif other.is_integer is False: 

return S.false 

def _union(self, other): 

intersect = Intersection(self, other) 

if intersect == self: 

return other 

elif intersect == other: 

return self 

def __iter__(self): 

yield S.Zero 

i = S.One 

while True: 

yield i 

yield -i 

i = i + 1 

@property 

def _inf(self): 

return -S.Infinity 

@property 

def _sup(self): 

return S.Infinity 

@property 

def _boundary(self): 

return self 

def _eval_imageset(self, f): 

expr = f.expr 

if not isinstance(expr, Expr): 

return 

if len(f.variables) > 1: 

return 

n = f.variables[0] 

# f(x) + c and f(-x) + c cover the same integers 

# so choose the form that has the fewest negatives 

c = f(0) 

fx = f(n) - c 

f_x = f(-n) - c 

neg_count = lambda e: sum(_coeff_isneg(_) for _ in Add.make_args(e)) 

if neg_count(f_x) < neg_count(fx): 

expr = f_x + c 

a = Wild('a', exclude=[n]) 

b = Wild('b', exclude=[n]) 

match = expr.match(a*n + b) 

if match and match[a]: 

# canonical shift 

expr = match[a]*n + match[b] % match[a] 

if expr != f.expr: 

return ImageSet(Lambda(n, expr), S.Integers) 

class Reals(with_metaclass(Singleton, Interval)): 

def __new__(cls): 

return Interval.__new__(cls, -S.Infinity, S.Infinity) 

def __eq__(self, other): 

return other == Interval(-S.Infinity, S.Infinity) 

def __hash__(self): 

return hash(Interval(-S.Infinity, S.Infinity)) 

class ImageSet(Set): 

""" 

Image of a set under a mathematical function. The transformation 

must be given as a Lambda function which has as many arguments 

as the elements of the set upon which it operates, e.g. 1 argument 

when acting on the set of integers or 2 arguments when acting on 

a complex region. 

This function is not normally called directly, but is called 

from `imageset`. 

Examples 

======== 

>>> from sympy import Symbol, S, pi, Dummy, Lambda 

>>> from sympy.sets.sets import FiniteSet, Interval 

>>> from sympy.sets.fancysets import ImageSet 

>>> x = Symbol('x') 

>>> N = S.Naturals 

>>> squares = ImageSet(Lambda(x, x**2), N) # {x**2 for x in N} 

>>> 4 in squares 

True 

>>> 5 in squares 

False 

>>> FiniteSet(0, 1, 2, 3, 4, 5, 6, 7, 9, 10).intersect(squares) 

{1, 4, 9} 

>>> square_iterable = iter(squares) 

>>> for i in range(4): 

... next(square_iterable) 

1 

4 

9 

16 

If you want to get value for `x` = 2, 1/2 etc. (Please check whether the 

`x` value is in `base_set` or not before passing it as args) 

>>> squares.lamda(2) 

4 

>>> squares.lamda(S(1)/2) 

1/4 

>>> n = Dummy('n') 

>>> solutions = ImageSet(Lambda(n, n*pi), S.Integers) # solutions of sin(x) = 0 

>>> dom = Interval(-1, 1) 

>>> dom.intersect(solutions) 

{0} 

See Also 

======== 

sympy.sets.sets.imageset 

""" 

def __new__(cls, lamda, base_set): 

if not isinstance(lamda, Lambda): 

raise ValueError('first argument must be a Lambda') 

if lamda is S.IdentityFunction: 

return base_set 

if not lamda.expr.free_symbols or not lamda.expr.args: 

return FiniteSet(lamda.expr) 

return Basic.__new__(cls, lamda, base_set) 

lamda = property(lambda self: self.args[0]) 

base_set = property(lambda self: self.args[1]) 

def __iter__(self): 

already_seen = set() 

for i in self.base_set: 

val = self.lamda(i) 

if val in already_seen: 

continue 

else: 

already_seen.add(val) 

yield val 

def _is_multivariate(self): 

return len(self.lamda.variables) > 1 

def _contains(self, other): 

from sympy.matrices import Matrix 

from sympy.solvers.solveset import solveset, linsolve 

from sympy.utilities.iterables import is_sequence, iterable, cartes 

L = self.lamda 

if is_sequence(other): 

if not is_sequence(L.expr): 

return S.false 

if len(L.expr) != len(other): 

raise ValueError(filldedent(''' 

Dimensions of other and output of Lambda are different.''')) 

elif iterable(other): 

raise ValueError(filldedent(''' 

`other` should be an ordered object like a Tuple.''')) 

solns = None 

if self._is_multivariate(): 

if not is_sequence(L.expr): 

# exprs -> (numer, denom) and check again 

# XXX this is a bad idea -- make the user 

# remap self to desired form 

return other.as_numer_denom() in self.func( 

Lambda(L.variables, L.expr.as_numer_denom()), self.base_set) 

eqs = [expr - val for val, expr in zip(other, L.expr)] 

variables = L.variables 

free = set(variables) 

if all(i.is_number for i in list(Matrix(eqs).jacobian(variables))): 

solns = list(linsolve([e - val for e, val in 

zip(L.expr, other)], variables)) 

else: 

syms = [e.free_symbols & free for e in eqs] 

solns = {} 

for i, (e, s, v) in enumerate(zip(eqs, syms, other)): 

if not s: 

if e != v: 

return S.false 

solns[vars[i]] = [v] 

continue 

elif len(s) == 1: 

sy = s.pop() 

sol = solveset(e, sy) 

if sol is S.EmptySet: 

return S.false 

elif isinstance(sol, FiniteSet): 

solns[sy] = list(sol) 

else: 

raise NotImplementedError 

else: 

raise NotImplementedError 

solns = cartes(*[solns[s] for s in variables]) 

else: 

x = L.variables[0] 

if isinstance(L.expr, Expr): 

# scalar -> scalar mapping 

solnsSet = solveset(L.expr - other, x) 

if solnsSet.is_FiniteSet: 

solns = list(solnsSet) 

else: 

msgset = solnsSet 

else: 

# scalar -> vector 

for e, o in zip(L.expr, other): 

solns = solveset(e - o, x) 

if solns is S.EmptySet: 

return S.false 

for soln in solns: 

try: 

if soln in self.base_set: 

break # check next pair 

except TypeError: 

if self.base_set.contains(soln.evalf()): 

break 

else: 

return S.false # never broke so there was no True 

return S.true 

if solns is None: 

raise NotImplementedError(filldedent(''' 

Determining whether %s contains %s has not 

been implemented.''' % (msgset, other))) 

for soln in solns: 

try: 

if soln in self.base_set: 

return S.true 

except TypeError: 

return self.base_set.contains(soln.evalf()) 

return S.false 

@property 

def is_iterable(self): 

return self.base_set.is_iterable 

def _intersect(self, other): 

from sympy.solvers.diophantine import diophantine 

if self.base_set is S.Integers: 

g = None 

if isinstance(other, ImageSet) and other.base_set is S.Integers: 

g = other.lamda.expr 

m = other.lamda.variables[0] 

elif other is S.Integers: 

m = g = Dummy('x') 

if g is not None: 

f = self.lamda.expr 

n = self.lamda.variables[0] 

# Diophantine sorts the solutions according to the alphabetic 

# order of the variable names, since the result should not depend 

# on the variable name, they are replaced by the dummy variables 

# below 

a, b = Dummy('a'), Dummy('b') 

f, g = f.subs(n, a), g.subs(m, b) 

solns_set = diophantine(f - g) 

if solns_set == set(): 

return EmptySet() 

solns = list(diophantine(f - g)) 

if len(solns) != 1: 

return 

# since 'a' < 'b', select soln for n 

nsol = solns[0][0] 

t = nsol.free_symbols.pop() 

return imageset(Lambda(n, f.subs(a, nsol.subs(t, n))), S.Integers) 

if other == S.Reals: 

from sympy.solvers.solveset import solveset_real 

from sympy.core.function import expand_complex 

if len(self.lamda.variables) > 1: 

return None 

f = self.lamda.expr 

n = self.lamda.variables[0] 

n_ = Dummy(n.name, real=True) 

f_ = f.subs(n, n_) 

re, im = f_.as_real_imag() 

im = expand_complex(im) 

return imageset(Lambda(n_, re), 

self.base_set.intersect( 

solveset_real(im, n_))) 

elif isinstance(other, Interval): 

from sympy.solvers.solveset import (invert_real, invert_complex, 

solveset) 

f = self.lamda.expr 

n = self.lamda.variables[0] 

base_set = self.base_set 

new_inf, new_sup = None, None 

if f.is_real: 

inverter = invert_real 

else: 

inverter = invert_complex 

g1, h1 = inverter(f, other.inf, n) 

g2, h2 = inverter(f, other.sup, n) 

if all(isinstance(i, FiniteSet) for i in (h1, h2)): 

if g1 == n: 

if len(h1) == 1: 

new_inf = h1.args[0] 

if g2 == n: 

if len(h2) == 1: 

new_sup = h2.args[0] 

# TODO: Design a technique to handle multiple-inverse 

# functions 

# Any of the new boundary values cannot be determined 

if any(i is None for i in (new_sup, new_inf)): 

return 

range_set = S.EmptySet 

if all(i.is_real for i in (new_sup, new_inf)): 

new_interval = Interval(new_inf, new_sup) 

range_set = base_set._intersect(new_interval) 

else: 

if other.is_subset(S.Reals): 

solutions = solveset(f, n, S.Reals) 

if not isinstance(range_set, (ImageSet, ConditionSet)): 

range_set = solutions._intersect(other) 

else: 

return 

if range_set is S.EmptySet: 

return S.EmptySet 

elif isinstance(range_set, Range) and range_set.size is not S.Infinity: 

range_set = FiniteSet(*list(range_set)) 

if range_set is not None: 

return imageset(Lambda(n, f), range_set) 

return 

else: 

return 

class Range(Set): 

""" 

Represents a range of integers. Can be called as Range(stop), 

Range(start, stop), or Range(start, stop, step); when stop is 

not given it defaults to 1. 

`Range(stop)` is the same as `Range(0, stop, 1)` and the stop value 

(juse as for Python ranges) is not included in the Range values. 

>>> from sympy import Range 

>>> list(Range(3)) 

[0, 1, 2] 

The step can also be negative: 

>>> list(Range(10, 0, -2)) 

[10, 8, 6, 4, 2] 

The stop value is made canonical so equivalent ranges always 

have the same args: 

>>> Range(0, 10, 3) 

Range(0, 12, 3) 

Infinite ranges are allowed. If the starting point is infinite, 

then the final value is ``stop - step``. To iterate such a range, 

it needs to be reversed: 

>>> from sympy import oo 

>>> r = Range(-oo, 1) 

>>> r[-1] 

0 

>>> next(iter(r)) 

Traceback (most recent call last): 

... 

ValueError: Cannot iterate over Range with infinite start 

>>> next(iter(r.reversed)) 

0 

Although Range is a set (and supports the normal set 

operations) it maintains the order of the elements and can 

be used in contexts where `range` would be used. 

>>> from sympy import Interval 

>>> Range(0, 10, 2).intersect(Interval(3, 7)) 

Range(4, 8, 2) 

>>> list(_) 

[4, 6] 

Athough slicing of a Range will always return a Range -- possibly 

empty -- an empty set will be returned from any intersection that 

is empty: 

>>> Range(3)[:0] 

Range(0, 0, 1) 

>>> Range(3).intersect(Interval(4, oo)) 

EmptySet() 

>>> Range(3).intersect(Range(4, oo)) 

EmptySet() 

""" 

is_iterable = True 

def __new__(cls, *args): 

from sympy.functions.elementary.integers import ceiling 

if len(args) == 1: 

if isinstance(args[0], range if PY3 else xrange): 

args = args[0].__reduce__()[1] # use pickle method 

# expand range 

slc = slice(*args) 

if slc.step == 0: 

raise ValueError("step cannot be 0") 

start, stop, step = slc.start or 0, slc.stop, slc.step or 1 

try: 

start, stop, step = [ 

w if w in [S.NegativeInfinity, S.Infinity] 

else sympify(as_int(w)) 

for w in (start, stop, step)] 

except ValueError: 

raise ValueError(filldedent(''' 

Finite arguments to Range must be integers; `imageset` can define 

other cases, e.g. use `imageset(i, i/10, Range(3))` to give 

[0, 1/10, 1/5].''')) 

if not step.is_Integer: 

raise ValueError(filldedent(''' 

Ranges must have a literal integer step.''')) 

if all(i.is_infinite for i in (start, stop)): 

if start == stop: 

# canonical null handled below 

start = stop = S.One 

else: 

raise ValueError(filldedent(''' 

Either the start or end value of the Range must be finite.''')) 

if start.is_infinite: 

end = stop 

else: 

ref = start if start.is_finite else stop 

n = ceiling((stop - ref)/step) 

if n <= 0: 

# null Range 

start = end = 0 

step = 1 

else: 

end = ref + n*step 

return Basic.__new__(cls, start, end, step) 

start = property(lambda self: self.args[0]) 

stop = property(lambda self: self.args[1]) 

step = property(lambda self: self.args[2]) 

@property 

def reversed(self): 

"""Return an equivalent Range in the opposite order. 

Examples 

======== 

>>> from sympy import Range 

>>> Range(10).reversed 

Range(9, -1, -1) 

""" 

if not self: 

return self 

return self.func( 

self.stop - self.step, self.start - self.step, -self.step) 

def _intersect(self, other): 

from sympy.functions.elementary.integers import ceiling, floor 

from sympy.functions.elementary.complexes import sign 

if other is S.Naturals: 

return self._intersect(Interval(1, S.Infinity)) 

if other is S.Integers: 

return self 

if other.is_Interval: 

if not all(i.is_number for i in other.args[:2]): 

return 

# In case of null Range, return an EmptySet. 

if self.size == 0: 

return S.EmptySet 

# trim down to self's size, and represent 

# as a Range with step 1. 

start = ceiling(max(other.inf, self.inf)) 

if start not in other: 

start += 1 

end = floor(min(other.sup, self.sup)) 

if end not in other: 

end -= 1 

return self.intersect(Range(start, end + 1)) 

if isinstance(other, Range): 

from sympy.solvers.diophantine import diop_linear 

from sympy.core.numbers import ilcm 

# non-overlap quick exits 

if not other: 

return S.EmptySet 

if not self: 

return S.EmptySet 

if other.sup < self.inf: 

return S.EmptySet 

if other.inf > self.sup: 

return S.EmptySet 

# work with finite end at the start 

r1 = self 

if r1.start.is_infinite: 

r1 = r1.reversed 

r2 = other 

if r2.start.is_infinite: 

r2 = r2.reversed 

# this equation represents the values of the Range; 

# it's a linear equation 

eq = lambda r, i: r.start + i*r.step 

# we want to know when the two equations might 

# have integer solutions so we use the diophantine 

# solver 

a, b = diop_linear(eq(r1, Dummy()) - eq(r2, Dummy())) 

# check for no solution 

no_solution = a is None and b is None 

if no_solution: 

return S.EmptySet 

# there is a solution 

# ------------------- 

# find the coincident point, c 

a0 = a.as_coeff_Add()[0] 

c = eq(r1, a0) 

# find the first point, if possible, in each range 

# since c may not be that point 

def _first_finite_point(r1, c): 

if c == r1.start: 

return c 

# st is the signed step we need to take to 

# get from c to r1.start 

st = sign(r1.start - c)*step 

# use Range to calculate the first point: 

# we want to get as close as possible to 

# r1.start; the Range will not be null since 

# it will at least contain c 

s1 = Range(c, r1.start + st, st)[-1] 

if s1 == r1.start: 

pass 

else: 

# if we didn't hit r1.start then, if the 

# sign of st didn't match the sign of r1.step 

# we are off by one and s1 is not in r1 

if sign(r1.step) != sign(st): 

s1 -= st 

if s1 not in r1: 

return 

return s1 

# calculate the step size of the new Range 

step = abs(ilcm(r1.step, r2.step)) 

s1 = _first_finite_point(r1, c) 

if s1 is None: 

return S.EmptySet 

s2 = _first_finite_point(r2, c) 

if s2 is None: 

return S.EmptySet 

# replace the corresponding start or stop in 

# the original Ranges with these points; the 

# result must have at least one point since 

# we know that s1 and s2 are in the Ranges 

def _updated_range(r, first): 

st = sign(r.step)*step 

if r.start.is_finite: 

rv = Range(first, r.stop, st) 

else: 

rv = Range(r.start, first + st, st) 

return rv 

r1 = _updated_range(self, s1) 

r2 = _updated_range(other, s2) 

# work with them both in the increasing direction 

if sign(r1.step) < 0: 

r1 = r1.reversed 

if sign(r2.step) < 0: 

r2 = r2.reversed 

# return clipped Range with positive step; it 

# can't be empty at this point 

start = max(r1.start, r2.start) 

stop = min(r1.stop, r2.stop) 

return Range(start, stop, step) 

else: 

return 

def _contains(self, other): 

if not self: 

return S.false 

if other.is_infinite: 

return S.false 

if not other.is_integer: 

return other.is_integer 

ref = self.start if self.start.is_finite else self.stop 

if (ref - other) % self.step: # off sequence 

return S.false 

return _sympify(other >= self.inf and other <= self.sup) 

def __iter__(self): 

if self.start in [S.NegativeInfinity, S.Infinity]: 

raise ValueError("Cannot iterate over Range with infinite start") 

elif self: 

i = self.start 

step = self.step 

while True: 

if (step > 0 and not (self.start <= i < self.stop)) or \ 

(step < 0 and not (self.stop < i <= self.start)): 

break 

yield i 

i += step 

def __len__(self):