Families

A Family is an associative container which models a family (f_i)_{i \in I}. Then, f[i] returns the element of the family indexed by i. Whenever available, set and combinatorial class operations (counting, iteration, listing) on the family are induced from those of the index set. Families should be created through the Family() function.

AUTHORS:

  • Nicolas Thiery (2008-02): initial release
  • Florent Hivert (2008-04): various fixes, cleanups and improvements.
class sage.sets.family.AbstractFamily

The abstract class for family

Any family belongs to a class which inherits from AbstractFamily.

hidden_keys()

Returns the hidden keys of the family, if any.

EXAMPLES:

sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
sage: f.hidden_keys()
[]
map(f, name=None)

Returns the family ( f(\mathtt{self}[i]) )_{i \in I}, where I is the index set of self.

TODO: good name?

EXAMPLES:

sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
sage: g = f.map(lambda x: x+'1')
sage: list(g)
['a1', 'b1', 'd1']
zip(f, other, name=None)

Given two families with same index set I (and same hidden keys if relevant), returns the family ( f(self[i], other[i]) )_{i \in I}

TODO: generalize to any number of families and merge with map?

EXAMPLES:

sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
sage: g = Family({3: '1', 4: '2', 7: '3'})
sage: h = f.zip(lambda x,y: x+y, g)
sage: list(h)
['a1', 'b2', 'd3']
sage.sets.family.Family(indices, function=None, hidden_keys=[], hidden_function=None, lazy=False, name=None)

A Family is an associative container which models a family (f_i)_{i \in I}. Then, f[i] returns the element of the family indexed by i. Whenever available, set and combinatorial class operations (counting, iteration, listing) on the family are induced from those of the index set.

There are several available implementations (classes) for different usages; Family serves as a factory, and will create instances of the appropriate classes depending on its arguments.

EXAMPLES:

In its simplest form, a list l or a tuple by itself is considered as the family (l[i]_{i \in I}) where I is the range 0\dots,len(l). So Family(l) returns the corresponding family.

sage: f = Family([1,2,3])
sage: f
Family (1, 2, 3)
sage: f = Family((1,2,3))
sage: f
Family (1, 2, 3)

A family can also be constructed from a dictionary t. The resulting family is very close to t, except that the elements of the family are the values of t. Here, we define the family (f_i)_{i \in \{3,4,7\}} with f_3=’a’, f_4=’b’, and f_7=’d’:

sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
sage: f
Finite family {3: 'a', 4: 'b', 7: 'd'}
sage: f[7]
'd'
sage: len(f)
3
sage: list(f)
['a', 'b', 'd']
sage: [ x for x in f ]
['a', 'b', 'd']
sage: f.keys()
[3, 4, 7]
sage: 'b' in f  
True
sage: 'e' in f
False

A family can also be constructed by its index set I and a function f, as in (f(i))_{i \in I}:

sage: f = Family([3,4,7], lambda i: 2*i)
sage: f
Finite family {3: 6, 4: 8, 7: 14}
sage: f.keys()
[3, 4, 7]
sage: f[7]
14
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]
sage: len(f)
3

By default, all images are computed right away, and stored in an internal dictionary:

sage: f = Family((3,4,7), lambda i: 2*i)
sage: f
Finite family {3: 6, 4: 8, 7: 14}

Note that this requires all the elements of the list to be hashable. One can ask instead for the images f(i) to be computed lazily, when needed:

sage: f = Family([3,4,7], lambda i: 2r*i, lazy=True)
sage: f
Lazy family (<lambda>(i))_{i in [3, 4, 7]}
sage: f[7]
14
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]

This allows in particular for modeling infinite families:

sage: f = Family(ZZ, lambda i: 2r*i, lazy=True)
sage: f
Lazy family (<lambda>(i))_{i in Integer Ring}
sage: f.keys()
Integer Ring
sage: f[1]
2
sage: f[-5]
-10
sage: i = iter(f)
sage: i.next(), i.next(), i.next(), i.next(), i.next()
(0, 2, -2, 4, -4)

Note that the lazy keyword parameter is only needed to force laziness. Usually it is automatically set to a correct default value (ie: False for finite data structures and true for CombinatorialClasses:

sage: f == Family(ZZ, lambda i: 2r*i)
True

Beware that for those kind of families len(f) is not supposed to work. As a replacement, use the .cardinality() method:

sage: f = Family(Permutations(3), attrcall("to_lehmer_code"))
sage: list(f)
[[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0], [2, 0, 0], [2, 1, 0]]
sage: f.cardinality()
6

Caveat: Only certain families with lazy behavior can be pickled. In particular, only functions that work with Sage’s pickle_function and unpickle_function (in sage.misc.fpickle) will correctly unpickle. The following two work:

sage: f = Family(Permutations(3), lambda p: p.to_lehmer_code()); f
Lazy family (<lambda>(i))_{i in Standard permutations of 3}
sage: f == loads(dumps(f))
True

sage: f = Family(Permutations(3), attrcall("to_lehmer_code")); f
Lazy family (i.to_lehmer_code())_{i in Standard permutations of 3}
sage: f == loads(dumps(f))
True

But this one don’t:

sage: def plus_n(n): return lambda x: x+n
sage: f = Family([1,2,3], plus_n(3), lazy=True); f
Lazy family (<lambda>(i))_{i in [1, 2, 3]}
sage: f == loads(dumps(f))
...
ValueError: Cannot pickle code objects from closures

Finally, it can occasionally be useful to add some hidden elements in a family, which are accessible as f[i], but do not appear in the keys or the container operations:

sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
sage: f
Finite family {3: 6, 4: 8, 7: 14}
sage: f.keys()
[3, 4, 7]
sage: f.hidden_keys()
[2]
sage: f[7]
14
sage: f[2]
4
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]
sage: len(f)
3

The following example illustrates when the function is actually called:

sage: def compute_value(i):
...       print('computing 2*'+str(i))
...       return 2*i
sage: f = Family([3,4,7], compute_value, hidden_keys=[2])
computing 2*3
computing 2*4
computing 2*7
sage: f
Finite family {3: 6, 4: 8, 7: 14}
sage: f.keys()
[3, 4, 7]
sage: f.hidden_keys()
[2]
sage: f[7]
14
sage: f[2]
computing 2*2
4
sage: f[2]
4
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]
sage: len(f)
3

Here is a close variant where the function for the hidden keys is different from that for the other keys:

sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2], hidden_function = lambda i: 3*i)
sage: f
Finite family {3: 6, 4: 8, 7: 14}
sage: f.keys()
[3, 4, 7]
sage: f.hidden_keys()
[2]
sage: f[7]
14
sage: f[2]
6
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]
sage: len(f)
3

Family behaves the same way with FiniteCombinatorialClass instances and lists. This feature will eventually disappear when FiniteCombinatorialClass won’t be needed anymore.

sage: f = Family(FiniteCombinatorialClass([1,2,3]))
sage: f
Combinatorial class with elements in [1, 2, 3]
sage: f = Family(FiniteCombinatorialClass([3,4,7]), lambda i: 2*i)
sage: f
Finite family {3: 6, 4: 8, 7: 14}
sage: f.keys()
[3, 4, 7]
sage: f[7]
14
sage: list(f)
[6, 8, 14]
sage: [x for x in f]
[6, 8, 14]
sage: len(f)
3

TESTS:

sage: f = Family({1:'a', 2:'b', 3:'c'})
sage: f
Finite family {1: 'a', 2: 'b', 3: 'c'}
sage: f[2]
'b'
sage: loads(dumps(f)) == f
True
sage: f = Family({1:'a', 2:'b', 3:'c'}, lazy=True)
Traceback (most recent call last):
ValueError: lazy keyword only makes sense together with function keyword !
sage: f = Family(range(1,27), lambda i: chr(i+96))
sage: f
    Finite family {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 10: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r', 19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'}
sage: f[2]
'b'

The factory Family is supposed to be idempotent. We test this feature here:

sage: from sage.sets.family import FiniteFamily, LazyFamily, TrivialFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
sage: g = Family(f)
sage: f == g
True

sage: f = Family([3,4,7], lambda i: 2r*i, hidden_keys=[2])
sage: g = Family(f)
sage: f == g
True

sage: f = LazyFamily([3,4,7], lambda i: 2r*i)
sage: g = Family(f)
sage: f == g
True

sage: f = TrivialFamily([3,4,7])
sage: g = Family(f)
sage: f == g
True
class sage.sets.family.FiniteFamily(dictionary, keys=None)

A FiniteFamily is an associative container which models a finite family (f_i)_{i \in I}. Its elements f_i are therefore its values. Instances should be created via the Family factory, which see for further examples and tests.

EXAMPLES: We define the family (f_i)_{i \in \{3,4,7\}} with f_3=a, f_4=b, and f_7=d

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})

Individual elements are accessible as in a usual dictionary:

sage: f[7]
'd'

And the other usual dictionary operations are also available:

sage: len(f)
3
sage: f.keys()
[3, 4, 7]

However f behaves as a container for the f_i‘s:

sage: list(f)
['a', 'b', 'd']
sage: [ x for x in f ]
['a', 'b', 'd']
__contains__(x)

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a'})
sage: 'a' in f
True
sage: 'b' in f
False
__getitem__(i)

Note that we can’t just do self.__getitem__ = dictionary.__getitem__ in the __init__ method since Python queries the object’s type/class for the special methods rather than querying the object itself.

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
sage: f[3]
'a'
__getstate__()

TESTS:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a'})
sage: f.__getstate__()
{'dictionary': {3: 'a'}}
__init__(dictionary, keys=None)

TESTS:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
sage: f == loads(dumps(f))
True

Check for bug #5538:

sage: d = {1:"a", 3:"b", 4:"c"}
sage: f = Family(d)
sage: d[2] = 'DD'
sage: f
Finite family {1: 'a', 3: 'b', 4: 'c'}
__iter__()

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a'})
sage: i = iter(f)
sage: i.next()
'a'
__len__()

Returns the number of elements in self.

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
sage: len(f)
3        
__setstate__(state)

TESTS:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a'})
sage: f.__setstate__({'dictionary': {4:'b'}})
sage: f
Finite family {4: 'b'}
_repr_()

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: FiniteFamily({3: 'a'})
Finite family {3: 'a'}
cardinality()

Returns the number of elements in self.

EXAMPLES:

sage: from sage.sets.family import FiniteFamily
sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
sage: f.cardinality()
3
class sage.sets.family.FiniteFamilyWithHiddenKeys(dictionary, hidden_keys, hidden_function)

A close variant of FiniteFamily where the family contains some hidden keys whose corresponding values are computed lazily (and remembered). Instances should be created via the Family factory, which see for examples and tests.

Caveat: Only instances of this class whose functions are compatible with sage.misc.fpickle can be pickled.

__getitem__(i)

EXAMPLES:

sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
sage: f[3]
6
sage: f[2]
4
sage: f[5]
...
KeyError
__getstate__()

TESTS:

sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
sage: d = f.__getstate__()
sage: d['hidden_keys']
[2]
__init__(dictionary, hidden_keys, hidden_function)

EXAMPLES:

sage: f = Family([3,4,7], lambda i: 2r*i, hidden_keys=[2])
sage: f == loads(dumps(f))
True
__setstate__(d)

TESTS:

sage: f = Family([3,4,7], lambda i: 2r*i, hidden_keys=[2])
sage: d = f.__getstate__()
sage: f = Family([4,5,6], lambda i: 2r*i, hidden_keys=[2])
sage: f.__setstate__(d)
sage: f.keys()
[3, 4, 7]
sage: f[3]
6
hidden_keys()

Returns self’s hidden keys.

EXAMPLES:

sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
sage: f.hidden_keys()
[2]
class sage.sets.family.LazyFamily(set, function, name=None)

A LazyFamily(I, f) is an associative container which models the (possibly infinite) family (f(i))_{i \in I}.

Instances should be created via the Family factory, which see for examples and tests.

__getitem__(i)

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2*i)
sage: f[3]
6

TESTS:

sage: f[5]
10
__getstate__()

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2r*i)
sage: d = f.__getstate__()
sage: d['set']
[3, 4, 7]

sage: f = LazyFamily(Permutations(3), lambda p: p.to_lehmer_code())
sage: f == loads(dumps(f))
True

sage: f = LazyFamily(Permutations(3), attrcall("to_lehmer_code"))
sage: f == loads(dumps(f))
True            
__init__(set, function, name=None)

TESTS:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2r*i); f
Lazy family (<lambda>(i))_{i in [3, 4, 7]}
sage: f == loads(dumps(f))
True

Check for bug #5538:

sage: l = [3,4,7]
sage: f = LazyFamily(l, lambda i: 2r*i);
sage: l[1] = 18
sage: f
Lazy family (<lambda>(i))_{i in [3, 4, 7]}
__iter__()

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2*i)
sage: [i for i in f]
[6, 8, 14]
__setstate__(d)

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2r*i)
sage: d = f.__getstate__()
sage: f = LazyFamily([4,5,6], lambda i: 2r*i)
sage: f.__setstate__(d)
sage: f.keys()
[3, 4, 7]
sage: f[3]
6
_repr_()

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: def fun(i): 2*i
sage: f = LazyFamily([3,4,7], fun); f
Lazy family (fun(i))_{i in [3, 4, 7]}

sage: f = Family(Permutations(3), attrcall("to_lehmer_code"), lazy=True); f
Lazy family (i.to_lehmer_code())_{i in Standard permutations of 3}

sage: f = LazyFamily([3,4,7], lambda i: 2*i); f
Lazy family (<lambda>(i))_{i in [3, 4, 7]}
cardinality()

Return the number of elements in self.

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2*i)
sage: f.cardinality()
3
keys()

Returns self’s keys.

EXAMPLES:

sage: from sage.sets.family import LazyFamily
sage: f = LazyFamily([3,4,7], lambda i: 2*i)
sage: f.keys()
[3, 4, 7]
class sage.sets.family.TrivialFamily(enumeration)

TrivialFamily(c) turn the container c into a family indexed by the set {0, \dots, len(c)}. The container c can be either a list or a tuple.

Instances should be created via the Family factory, which see for examples and tests.

__getitem__(i)

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: f[1]
4        
__getstate__()

TESTS:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: f.__getstate__()
{'_enumeration': (3, 4, 7)}
__init__(enumeration)

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily((3,4,7)); f
Family (3, 4, 7)
sage: f = TrivialFamily([3,4,7]); f
Family (3, 4, 7)
sage: f == loads(dumps(f))
True
__iter__()

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: [i for i in f]
[3, 4, 7]
__setstate__(state)

TESTS:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: f.__setstate__({'_enumeration': (2, 4, 8)})
sage: f
Family (2, 4, 8)
_repr_()

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7]); f
Family (3, 4, 7)
cardinality()

Return the number of elements in self.

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: f.cardinality()
3
keys()

Returns self’s keys.

EXAMPLES:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily([3,4,7])
sage: f.keys()
[0, 1, 2]

Previous topic

The set of prime numbers

Next topic

Base class for parent objects

This Page