Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Streams or Infinite Arrays
This code is based on the work of Ralf Hemmecke and Martin Rubey's Aldor-Combinat, which can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/aldor/combinat/index.html. In particular, the relevant section for this file can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatse12.html. """ import types from sage.structure.sage_object import SageObject
def _integers_from(n): """ Returns a generator for the integers starting at n.
EXAMPLES::
sage: from sage.combinat.species.stream import _integers_from sage: g = _integers_from(5) sage: [next(g) for i in range(5)] [5, 6, 7, 8, 9] """
def _apply_function(func, list): """ Returns an iterator for func(i) for i in list.
EXAMPLES::
sage: from sage.combinat.species.stream import _apply_function sage: def square(l): ....: l.append(l[-1]^2) ....: return l[-1] ... sage: l = [2] sage: g = _apply_function(square, l) sage: [next(g) for i in range(5)] [4, 16, 256, 65536, 4294967296] """ break
def Stream(x=None, const=None): """ Returns a stream.
EXAMPLES: We can create a constant stream by just passing a
::
sage: from sage.combinat.species.stream import Stream sage: s = Stream(const=0) sage: [s[i] for i in range(10)] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] """
class Stream_class(SageObject): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: from builtins import zip sage: s = Stream(const=0) sage: len(s) 1 sage: [x for (x,i) in zip(s, range(4))] [0, 0, 0, 0] sage: len(s) 1
::
sage: s = Stream(const=4) sage: g = iter(s) sage: l1 = [x for (x,i) in zip(g, range(10))] sage: l = [4 for k in range(10)] sage: l == l1 True
::
sage: h = lambda l: 1 if len(l) < 2 else l[-1] + l[-2] sage: fib = Stream(h) sage: [x for (x,i) in zip(fib, range(11))] [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
::
sage: r = [4, 3, 5, 2, 6, 1, 1, 1, 1, 1] sage: l = [4, 3, 5, 2, 6, 1] sage: s = Stream(l) sage: s[3] = -1 sage: [x for (x,i) in zip(s, r)] [4, 3, 5, -1, 6, 1, 1, 1, 1, 1] sage: s[5] = -2 sage: [x for (x,i) in zip(s, r)] [4, 3, 5, -1, 6, -2, 1, 1, 1, 1] sage: s[6] = -3 sage: [x for (x,i) in zip(s, r)] [4, 3, 5, -1, 6, -2, -3, 1, 1, 1] sage: s[8] = -4 sage: [x for (x,i) in zip(s, r)] [4, 3, 5, -1, 6, -2, -3, 1, -4, 1] sage: a = Stream(const=0) sage: a[2] = 3 sage: [x for (x,i) in zip(a, range(4))] [0, 0, 3, 0] """
def __init__(self, gen=None, const=None, func=None): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream_class, Stream sage: s = Stream_class(const=4) sage: loads(dumps(s)) <sage.combinat.species.stream.Stream_class object at ...>
::
sage: sorted(s.__dict__.items()) [('_constant', 4), ('_gen', None), ('_last_index', 0), ('_list', [4]), ('end_reached', True)]
::
sage: s = Stream(ZZ) sage: sorted(s.__dict__.items()) [('_constant', None), ('_gen', <generator object at 0x...>), ('_last_index', -1), ('_list', []), ('end_reached', False)] """ #We define self._list up here so that #_apply_function can make use of it if #it needs to.
raise ValueError("you cannot specify both a function and a generator")
#Constant stream else:
def __setitem__(self, i, t): """ Sets the ith entry of self to t.
EXAMPLES::
sage: from sage.combinat.species.stream import Stream
::
sage: s = Stream(const=0) sage: s[5] 0 sage: s.data() [0] sage: s[5] = 5 sage: s[5] 5 sage: s.data() [0, 0, 0, 0, 0, 5]
::
sage: s = Stream(ZZ) sage: s[10] -5 sage: s.data() [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5] sage: s[10] = 10 sage: s.data() [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, 10] """ #Compute all of the coefficients up to (and including) the ith one
#If we are here, we can just change the entry in self._list else: #If we are here, then the stream has become constant. We just #extend self._list with self._constant and then change the #last entry.
def set_gen(self, gen): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: from builtins import zip sage: fib = Stream() sage: def g(): ....: yield 1 ....: yield 1 ....: n = 0 ....: while True: ....: yield fib[n] + fib[n+1] ....: n += 1
::
sage: fib.set_gen(g()) sage: [x for (x,i) in zip(fib, range(11))] [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
::
sage: l = [4,3,5,2,6,1] sage: s = Stream(l) sage: s[3] 2 sage: len(s) 4 sage: g = iter(l) sage: s.set_gen(g) sage: s[5] 3 sage: len(s) 6 """
def map(self, f): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream(ZZ) sage: square = lambda x: x^2 sage: ss = s.map(square) sage: [ss[i] for i in range(10)] [0, 1, 1, 4, 4, 9, 9, 16, 16, 25]
TESTS::
sage: from builtins import zip sage: f = lambda l: 0 if len(l) == 0 else l[-1] + 1 sage: o = Stream(f) sage: [x for (x,i) in zip(o, range(10))] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: double = lambda z: 2*z sage: t = o.map(double) sage: [x for (x,i) in zip(t, range(10))] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
::
sage: double = lambda z: 2*z sage: o = Stream([0,1,2,3]) sage: [x for (x,i) in zip(o, range(6))] [0, 1, 2, 3, 3, 3] sage: t = o.map(double) sage: [x for (x,i) in zip(t, range(6))] [0, 2, 4, 6, 6, 6] """
def __getitem__(self, i): """ Returns the ith entry of self.
EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream(ZZ) sage: [s[i] for i in range(10)] [0, 1, -1, 2, -2, 3, -3, 4, -4, 5] sage: s[1] 1
::
sage: s = Stream([1,2,3]) sage: [s[i] for i in range(10)] [1, 2, 3, 3, 3, 3, 3, 3, 3, 3]
::
sage: s = Stream(QQ) sage: s[10] -3 """ else: raise IndexError("out of position") else:
def __iter__(self): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream([1,2,3]) sage: g = iter(s) sage: [next(g) for i in range(5)] [1, 2, 3, 3, 3] """ break
def __len__(self): """ Returns the number of coefficients computed so far.
EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: l = [4,3,5,7,4,1,9,7] sage: s = Stream(l) sage: s[3] 7 sage: len(s) 4 sage: s[3] 7 sage: len(s) 4 sage: s[1] 3 sage: len(s) 4 sage: s[4] 4 sage: len(s) 5
TESTS::
sage: l = ['Hello', ' ', 'World', '!'] sage: s = Stream(l) sage: len(s) 0 sage: s[2] 'World' sage: len(s) 3 sage: u = "" sage: for i in range(len(s)): u += s[i] sage: u 'Hello World' sage: v = "" sage: for i in range(10): v += s[i] sage: v 'Hello World!!!!!!!' sage: len(s) 4 """
number_computed = __len__
def data(self): """ Returns a list of all the coefficients computed so far.
EXAMPLES::
sage: from sage.combinat.species.stream import Stream, _integers_from sage: s = Stream(_integers_from(3)) sage: s.data() [] sage: s[5] 8 sage: s.data() [3, 4, 5, 6, 7, 8] """
def is_constant(self): """ Returns True if and only if
EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream([1,2,3]) sage: s.is_constant() False sage: s[3] 3 sage: s.data() [1, 2, 3] sage: s.is_constant() True
TESTS::
sage: l = [2,3,5,7,11,0] sage: s = Stream(l) sage: s.is_constant() False sage: s[3] 7 sage: s.is_constant() False sage: s[5] 0 sage: s.is_constant() False sage: s[6] 0 sage: s.is_constant() True
::
sage: s = Stream(const='I am constant.') sage: s.is_constant() True """
def stretch(self, k): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream(range(1, 10)) sage: s2 = s.stretch(2) sage: [s2[i] for i in range(10)] [1, 0, 2, 0, 3, 0, 4, 0, 5, 0] """
def _stretch_gen(self, k): """ EXAMPLES::
sage: from sage.combinat.species.stream import Stream sage: s = Stream(range(1, 10)) sage: g = s._stretch_gen(2) sage: [next(g) for i in range(10)] [1, 0, 2, 0, 3, 0, 4, 0, 5, 0] """ |