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#
Bases:
sage.structure.parent.Parent
The abstract class for family
Any family belongs to a class which inherits from
AbstractFamily
.Returns the hidden keys of the family, if any.
EXAMPLES:
sage: f = Family({3: 'a', 4: 'b', 7: 'd'}) sage: f.hidden_keys() []
- inverse_family()#
Returns the inverse family, with keys and values exchanged. This presumes that there are no duplicate values in
self
.This default implementation is not lazy and therefore will only work with not too big finite families. It is also cached for the same reason:
sage: Family({3: 'a', 4: 'b', 7: 'd'}).inverse_family() Finite family {'a': 3, 'b': 4, 'd': 7} sage: Family((3,4,7)).inverse_family() Finite family {3: 0, 4: 1, 7: 2}
- items()#
Return an iterator for key-value pairs.
A key can only appear once, but if the function is not injective, values may appear multiple times.
EXAMPLES:
sage: f = Family([-2, -1, 0, 1, 2], abs) sage: list(f.items()) [(-2, 2), (-1, 1), (0, 0), (1, 1), (2, 2)]
- keys()#
Return the keys of the family.
EXAMPLES:
sage: f = Family({3: 'a', 4: 'b', 7: 'd'}) sage: sorted(f.keys()) [3, 4, 7]
- 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']
- values()#
Return the elements (values) of this family.
EXAMPLES:
sage: f = Family(["c", "a", "b"], lambda x: x + x) sage: sorted(f.values()) ['aa', 'bb', 'cc']
- 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']
- class sage.sets.family.EnumeratedFamily(enumset)#
Bases:
sage.sets.family.LazyFamily
EnumeratedFamily
turns an enumerated setc
into a family indexed by the set \(\{0,\dots, |c|-1\}\) (orNN
if \(|c|\) is countably infinite).Instances should be created via the
Family()
factory. See its documentation for examples and tests.- cardinality()#
Return the number of elements in self.
EXAMPLES:
sage: from sage.sets.family import EnumeratedFamily sage: f = EnumeratedFamily(Permutations(3)) sage: f.cardinality() 6 sage: f = Family(NonNegativeIntegers()) sage: f.cardinality() +Infinity
- 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.
INPUT:
indices
– the indices for the familyfunction
– (optional) the function \(f\) applied to all visible indices; the default is the identity functionhidden_keys
– (optional) a list of hidden indices that can be accessed throughmy_family[i]
hidden_function
– (optional) a function for the hidden indiceslazy
– boolean (default:False
); whether the family is lazily created or not; if the indices are infinite, then this is automatically madeTrue
name
– (optional) the name of the function; only used when the family is lazily created via a function
EXAMPLES:
In its simplest form, a list \(l = [l_0, l_1, \ldots, l_{\ell}]\) or a tuple by itself is considered as the family \((l_i)_{i \in I}\) where \(I\) is the set \(\{0, \ldots, \ell\}\) where \(\ell\) is
len(l) - 1
. SoFamily(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)
Instead of a list you can as well pass any iterable object:
sage: f = Family(2*i+1 for i in [1,2,3]) sage: f Family (3, 5, 7)
A family can also be constructed from a dictionary
t
. The resulting family is very close tot
, except that the elements of the family are the values oft
. 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: 2*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: 2*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: next(i), next(i), next(i), next(i), next(i) (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 andTrue
for enumerated sets:sage: f == Family(ZZ, lambda i: 2*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 does not:
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)) Traceback (most recent call last): ... 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 accept finite and infinite EnumeratedSets as input:
sage: f = Family(FiniteEnumeratedSet([1,2,3])) sage: f Family (1, 2, 3) sage: f = Family(NonNegativeIntegers()) sage: f Family (Non negative integers)
sage: f = Family(FiniteEnumeratedSet([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
- class sage.sets.family.FiniteFamily(dictionary, keys=None)#
Bases:
sage.sets.family.AbstractFamily
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 theFamily()
factory. See its documentation for 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']
The order of the elements can be specified using the
keys
optional argument:sage: f = FiniteFamily({"a": "aa", "b": "bb", "c" : "cc" }, keys = ["c", "a", "b"]) sage: list(f) ['cc', 'aa', 'bb']
- 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
- has_key(k)#
Returns whether
k
is a key ofself
EXAMPLES:
sage: Family({"a":1, "b":2, "c":3}).has_key("a") True sage: Family({"a":1, "b":2, "c":3}).has_key("d") False
- keys()#
Returns the index set of this family
EXAMPLES:
sage: f = Family(["c", "a", "b"], lambda x: x+x) sage: f.keys() ['c', 'a', 'b']
- values()#
Returns the elements of this family
EXAMPLES:
sage: f = Family(["c", "a", "b"], lambda x: x+x) sage: f.values() ['cc', 'aa', 'bb']
- class sage.sets.family.FiniteFamilyWithHiddenKeys(dictionary, hidden_keys, hidden_function, keys=None)#
Bases:
sage.sets.family.FiniteFamily
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 theFamily()
factory. See its documentation for examples and tests.Caveat: Only instances of this class whose functions are compatible with
sage.misc.fpickle
can be pickled.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)#
Bases:
sage.sets.family.AbstractFamily
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. See its documentation for examples and tests.- 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 sage: l = LazyFamily(NonNegativeIntegers(), lambda i: 2*i) sage: l.cardinality() +Infinity
- 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)#
Bases:
sage.sets.family.AbstractFamily
TrivialFamily
turns a list/tuple \(c\) into a family indexed by the set \(\{0, \dots, |c|-1\}\).Instances should be created via the
Family()
factory. See its documentation for examples and tests.- 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]