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.

sage.combinat.species.stream.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 sage.combinat.species.stream.Stream_class(gen=None, const=None, func=None)

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: from itertools import izip
sage: s = Stream(const=0)
sage: len(s)
1
sage: [x for (x,i) in izip(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 izip(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 izip(fib, range(11))]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
sage: s = Stream()
sage: l = Stream([1, 0])
sage: y = Stream([0,1,0])
sage: s.set_gen(iter(l + y * s * s))
sage: [x for (x,i) in izip(s, range(6))]
[1, 1, 2, 5, 14, 42]
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 izip(s, r)]
[4, 3, 5, -1, 6, 1, 1, 1, 1, 1]
sage: s[5] = -2
sage: [x for (x,i) in izip(s, r)]
[4, 3, 5, -1, 6, -2, 1, 1, 1, 1]
sage: s[6] = -3
sage: [x for (x,i) in izip(s, r)]
[4, 3, 5, -1, 6, -2, -3, 1, 1, 1]
sage: s[8] = -4
sage: [x for (x,i) in izip(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 izip(a, range(4))]
[0, 0, 3, 0]
__add__(s)

Returns the sum of two streams.

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: s = Stream(ZZ)
sage: ss = s + s
sage: [ss[i] for i in range(10)]
[0, 2, -2, 4, -4, 6, -6, 8, -8, 10]
__getitem__(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
__init__(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))
<class 'sage.combinat.species.stream.Stream_class'>
sage: list(sorted(s.__dict__.iteritems()))
[('_constant', 4),
 ('_gen', None),
 ('_last_index', 0),
 ('_list', [4]),
 ('end_reached', True)]
sage: s = Stream(ZZ)
sage: list(sorted(s.__dict__.iteritems()))
[('_constant', None),
 ('_gen', <generator object iterator at 0x...>),
 ('_last_index', -1),
 ('_list', []),
 ('end_reached', False)]
__iter__()

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: s = Stream([1,2,3])
sage: g = iter(s)
sage: [g.next() for i in range(5)]
[1, 2, 3, 3, 3]
__len__()

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
__mul__(s)

Returns the product of two streams.

EXAMPLES: We can use a stream to represent the polynomial 1+x and use it to compute the coefficients of (1+x)2.

sage: from sage.combinat.species.stream import Stream
sage: s = Stream([1,1,0])
sage: ss = s*s
sage: [ss[i] for i in range(5)]
[1, 2, 1, 0, 0]
__setitem__(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]
__weakref__
list of weak references to the object (if defined)
_stretch_gen(k)

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: s = Stream(range(1, 10))
sage: g = s._stretch_gen(2)
sage: [g.next() for i in range(10)]
[1, 0, 2, 0, 3, 0, 4, 0, 5, 0]
_times_naive(s, n)

Returns the nth entry in the product of self and s via the naive multiplication algorithm. Note that this requires that all entries for self and s in range(n+1) be computed.

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: s = Stream([1,1,0])
sage: s._times_naive(s, 0)
1
sage: s._times_naive(s, 1)
2
sage: s._times_naive(s, 2)
1
data()

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]
is_constant()

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
map(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 itertools import izip
sage: f = lambda l: 0 if len(l) == 0 else l[-1] + 1
sage: o = Stream(f)
sage: [x for (x,i) in izip(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 izip(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 izip(o, range(6))]
[0, 1, 2, 3, 3, 3]
sage: t = o.map(double)
sage: [x for (x,i) in izip(t, range(6))]
[0, 2, 4, 6, 6, 6]
number_computed()

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
set_gen(gen)

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: from itertools import izip
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 izip(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
stretch(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]
sage.combinat.species.stream._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: [g.next() for i in range(5)]
[4, 16, 256, 65536, 4294967296]
sage.combinat.species.stream._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: [g.next() for i in range(5)]
[5, 6, 7, 8, 9]

Previous topic

Combinatorial Species

Next topic

Series Order

This Page