Integer Range

AUTHORS:

  • Nicolas Borie (2010-03): First release.
  • Florent Hivert (2010-03): Added a class factory + cardinality method.
  • Vincent Delecroix (2012-02): add methods rank/unrank, make it complient with Python int.
class sage.sets.integer_range.IntegerRange

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

The class of Integer ranges

Returns an enumerated set containing an arithmetic progression of integers.

INPUT:

  • begin – an integer, Infinity or -Infinity
  • end – an integer, Infinity or -Infinity
  • step – a non zero integer (default to 1)
  • middle_point – an integer inside the set (default to None)

OUTPUT:

A parent in the category FiniteEnumeratedSets() or InfiniteEnumeratedSets() depending on the arguments defining self.

IntegerRange(i, j) returns the set of \(\{i, i+1, i+2, \dots , j-1\}\). start (!) defaults to 0. When step is given, it specifies the increment. The default increment is \(1\). IntegerRange allows begin and end to be infinite.

IntegerRange is designed to have similar interface Python range. However, whereas range accept and returns Python int, IntegerRange deals with Integer.

If middle_point is given, then the elements are generated starting from it, in a alternating way: \(\{m, m+1, m-2, m+2, m-2 \dots \}\).

EXAMPLES:

sage: list(IntegerRange(5))
[0, 1, 2, 3, 4]
sage: list(IntegerRange(2,5))
[2, 3, 4]
sage: I = IntegerRange(2,100,5); I
{2, 7, ..., 97}
sage: list(I)
[2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 87, 92, 97]
sage: I.category()
Category of facade finite enumerated sets
sage: I[1].parent()
Integer Ring

When begin and end are both finite, IntegerRange(begin, end, step) is the set whose list of elements is equivalent to the python construction range(begin, end, step):

sage: list(IntegerRange(4,105,3)) == range(4,105,3)
True
sage: list(IntegerRange(-54,13,12)) == range(-54,13,12)
True

Except for the type of the numbers:

sage: type(IntegerRange(-54,13,12)[0]), type(range(-54,13,12)[0])
(<type 'sage.rings.integer.Integer'>, <type 'int'>)

When begin is finite and end is +Infinity, self is the infinite arithmetic progression starting from the begin by step step:

sage: I = IntegerRange(54,Infinity,3); I
{54, 57, ...}
sage: I.category()
Category of facade infinite enumerated sets
sage: p = iter(I)
sage: (p.next(), p.next(), p.next(), p.next(), p.next(), p.next())
(54, 57, 60, 63, 66, 69)

sage: I = IntegerRange(54,-Infinity,-3); I
{54, 51, ...}
sage: I.category()
Category of facade infinite enumerated sets
sage: p = iter(I)
sage: (p.next(), p.next(), p.next(), p.next(), p.next(), p.next())
(54, 51, 48, 45, 42, 39)

When begin and end are both infinite, you will have to specify the extra argument middle_point. self is then defined by a point and a progression/regression setting by step. The enumeration is done this way: (let us call \(m\) the middle_point) \(\{m, m+step, m-step, m+2step, m-2step, m+3step, \dots \}\):

sage: I = IntegerRange(-Infinity,Infinity,37,-12); I
Integer progression containing -12 with increment 37 and bounded with -Infinity and +Infinity
sage: I.category()
Category of facade infinite enumerated sets
sage: -12 in I
True
sage: -15 in I
False
sage: p = iter(I)
sage: (p.next(), p.next(), p.next(), p.next(), p.next(), p.next(), p.next(), p.next())
(-12, 25, -49, 62, -86, 99, -123, 136)

It is also possible to use the argument middle_point for other cases, finite or infinite. The set will be the same as if you didn’t give this extra argument but the enumeration will begin with this middle_point:

sage: I = IntegerRange(123,-12,-14); I
{123, 109, ..., -3}
sage: list(I)
[123, 109, 95, 81, 67, 53, 39, 25, 11, -3]
sage: J = IntegerRange(123,-12,-14,25); J
Integer progression containing 25 with increment -14 and bounded with 123 and -12
sage: list(J)
[25, 11, 39, -3, 53, 67, 81, 95, 109, 123]

Remember that, like for range, if you define a non empty set, begin is supposed to be included and end is supposed to be excluded. In the same way, when you define a set with a middle_point, the begin bound will be supposed to be included and the end bound supposed to be excluded:

sage: I = IntegerRange(-100,100,10,0)
sage: J = range(-100,100,10)
sage: 100 in I
False
sage: 100 in J
False
sage: -100 in I
True
sage: -100 in J
True
sage: list(I)
[0, 10, -10, 20, -20, 30, -30, 40, -40, 50, -50, 60, -60, 70, -70, 80, -80, 90, -90, -100]

Note

The input is normalized so that:

sage: IntegerRange(1, 6, 2) is IntegerRange(1, 7, 2)
True
sage: IntegerRange(1, 8, 3) is IntegerRange(1, 10, 3)
True

TESTS:

sage: # Some category automatic tests
sage: TestSuite(IntegerRange(2,100,3)).run()
sage: TestSuite(IntegerRange(564,-12,-46)).run()
sage: TestSuite(IntegerRange(2,Infinity,3)).run()
sage: TestSuite(IntegerRange(732,-Infinity,-13)).run()
sage: TestSuite(IntegerRange(-Infinity,Infinity,3,2)).run()
sage: TestSuite(IntegerRange(56,Infinity,12,80)).run()
sage: TestSuite(IntegerRange(732,-12,-2743,732)).run()
sage: # 20 random tests: range and IntegerRange give the same set for finite cases
sage: for i in range(20):
...       begin = Integer(randint(-300,300))
...       end = Integer(randint(-300,300))
...       step = Integer(randint(-20,20))
...       if step == 0:
...           step = Integer(1)
...       assert list(IntegerRange(begin, end, step)) == range(begin, end, step)
sage: # 20 random tests: range and IntegerRange with middle point for finite cases
sage: for i in range(20):
...       begin = Integer(randint(-300,300))
...       end = Integer(randint(-300,300))
...       step = Integer(randint(-15,15))
...       if step == 0:
...           step = Integer(-3)
...       I = IntegerRange(begin, end, step)
...       if I.cardinality() == 0:
...           assert len(range(begin, end, step)) == 0
...       else:
...           TestSuite(I).run()
...           L1 = list(IntegerRange(begin, end, step, I.an_element()))
...           L2 = range(begin, end, step)
...           L1.sort()
...           L2.sort()
...           assert L1 == L2

Thanks to trac ticket #8543 empty integer range are allowed:

sage: TestSuite(IntegerRange(0, 5, -1)).run()
element_class

alias of Integer

class sage.sets.integer_range.IntegerRangeEmpty(elements)

Bases: sage.sets.integer_range.IntegerRange, sage.sets.finite_enumerated_set.FiniteEnumeratedSet

A singleton class for empty integer ranges

See IntegerRange for more details.

class sage.sets.integer_range.IntegerRangeFinite(begin, end, step=1)

Bases: sage.sets.integer_range.IntegerRange

The class of finite enumerated sets of integers defined by finite arithmetic progressions

See IntegerRange for more details.

cardinality()

Return the cardinality of self

EXAMPLES:

sage: IntegerRange(123,12,-4).cardinality()
28
sage: IntegerRange(-57,12,8).cardinality()
9
sage: IntegerRange(123,12,4).cardinality()
0
rank(x)

EXAMPLES:

sage: I = IntegerRange(-57,36,8)
sage: I.rank(23)
10
sage: I.unrank(10)
23
sage: I.rank(22)
Traceback (most recent call last):
...
IndexError: 22 not in self
sage: I.rank(87)
Traceback (most recent call last):
...
IndexError: 87 not in self
unrank(i)

Return the i-th elt of this integer range.

EXAMPLES:

sage: I=IntegerRange(1,13,5)
sage: I[0], I[1], I[2]
(1, 6, 11)
sage: I[3]
Traceback (most recent call last):
...
IndexError: out of range
sage: I[-1]
11
sage: I[-4]
Traceback (most recent call last):
...
IndexError: out of range

sage: I = IntegerRange(13,1,-1)
sage: l = I.list()
sage: [I[i] for i in xrange(I.cardinality())] == l
True
sage: l.reverse()
sage: [I[i] for i in xrange(-1,-I.cardinality()-1,-1)] == l
True
class sage.sets.integer_range.IntegerRangeFromMiddle(begin, end, step=1, middle_point=1)

Bases: sage.sets.integer_range.IntegerRange

The class of finite or infinite enumerated sets defined with an inside point, a progression and two limits.

See IntegerRange for more details.

next(elt)

Return the next element of elt in self.

EXAMPLES:

sage: from sage.sets.integer_range import IntegerRangeFromMiddle
sage: I = IntegerRangeFromMiddle(-100,100,10,0)
sage: (I.next(0), I.next(10), I.next(-10), I.next(20), I.next(-100))
(10, -10, 20, -20, None)
sage: I = IntegerRangeFromMiddle(-Infinity,Infinity,10,0)
sage: (I.next(0), I.next(10), I.next(-10), I.next(20), I.next(-100))
(10, -10, 20, -20, 110)
sage: I.next(1)
Traceback (most recent call last):
...
LookupError: 1 not in Integer progression containing 0 with increment 10 and bounded with -Infinity and +Infinity
class sage.sets.integer_range.IntegerRangeInfinite(begin, step=1)

Bases: sage.sets.integer_range.IntegerRange

The class of infinite enumerated sets of integers defined by infinite arithmetic progressions.

See IntegerRange for more details.

rank(x)

EXAMPLES:

sage: I = IntegerRange(-57,Infinity,8)
sage: I.rank(23)
10
sage: I.unrank(10)
23
sage: I.rank(22)
Traceback (most recent call last):
...
IndexError: 22 not in self
unrank(i)

Returns the i-th element of self.

EXAMPLES:

sage: I = IntegerRange(-8,Infinity,3)
sage: I.unrank(1)
-5

Previous topic

Data structures for maps between finite sets

Next topic

Positive Integers

This Page