Iterators over finite submodules of a \(\ZZ\)-module¶
We iterate over the elements of a finite \(\ZZ\)-module. The action of \(\ZZ\) must be the natural one.
This class is intended to provide optimizations for the
sage.free_module.FreeModule_generic:__iter__()
method.
AUTHORS:
Thomas Feulner (2012-08-31): initial version
Punarbasu Purkayastha (2012-11-09): replaced the loop with recursion
Thomas Feulner (2012-11-09): added functionality to enumerate cosets, FiniteFieldsubspace_projPoint_iterator
EXAMPLES:
sage: from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
sage: F.<x,y,z> = FreeAlgebra(GF(3),3)
sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3])
sage: list(iter)
[0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y]
There is a specialization for subspaces over finite fields:
sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
sage: A = random_matrix(GF(4, 'a'), 5, 100)
sage: iter = FiniteFieldsubspace_iterator(A)
sage: len(list(iter))
1024
The module also allows the iteration over cosets:
sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
sage: A = random_matrix(GF(4, 'a'), 5, 100)
sage: v = random_vector(GF(4, 'a'), 100)
sage: iter = FiniteFieldsubspace_iterator(A, v)
sage: len(list(iter))
1024
-
class
sage.modules.finite_submodule_iter.
FiniteFieldsubspace_iterator
¶ Bases:
sage.modules.finite_submodule_iter.FiniteZZsubmodule_iterator
This class implements an iterator over the subspace of a vector space over a finite field. The subspace is generated by
basis
.INPUT:
basis
– a list of vectors or a matrix with elements over a finite field. If a matrix is provided then it is not checked whether the matrix is full ranked. Similarly, if a list of vectors is provided, then the linear independence of the vectors is not checked.coset_rep
(optional) – a vector in the same ambient space, if one aims to compute a coset of the vector space given bybasis
.immutable
(optional; default:False
) – set it toTrue
to return immutable vectors.
EXAMPLES:
sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator sage: A = random_matrix(GF(2), 10, 100) sage: iter = FiniteFieldsubspace_iterator(A) sage: len(list(iter)) 1024 sage: X = random_matrix(GF(4, 'a'), 7, 100).row_space() sage: s = list(X) # long time (5s on sage.math, 2013) sage: t = list(FiniteFieldsubspace_iterator(X.basis())) # takes 0.31s sage: sorted(t) == sorted(s) # long time True
-
class
sage.modules.finite_submodule_iter.
FiniteFieldsubspace_projPoint_iterator
¶ Bases:
object
This class implements an iterator over the projective points of a vector space over a finite field. The vector space is generated by
basis
and need not to be equal to the full ambient space.A projective point (= one dimensional subspace) \(P\) will be represented by a generator \(p\). To ensure that all \(p\) will be normalized you can set the optional argument
normalize
toTrue
.INPUT:
basis
– a list of vectors or a matrix with elements over a finite field. If a matrix is provided then it is not checked whether the matrix is full ranked. Similarly, if a list of vectors is provided, then the linear independence of the vectors is not checked.normalize
(optional; default:False
) – boolean which indicates if the returned vectors should be normalized, i.e. the first nonzero coordinate is equal to 1.immutable
(optional; default:False
) – set it toTrue
to return immutable vectors.
EXAMPLES:
sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator, FiniteFieldsubspace_projPoint_iterator sage: A = random_matrix(GF(4, 'a'), 5, 100) sage: a = len(list(FiniteFieldsubspace_iterator(A))) sage: b = len(list(FiniteFieldsubspace_projPoint_iterator(A))) sage: b == (a-1)/3 True
Prove that the option
normalize == True
will only return normalized vectors.sage: all(x.monic() == x for x in FiniteFieldsubspace_projPoint_iterator(A, True)) True
-
class
sage.modules.finite_submodule_iter.
FiniteZZsubmodule_iterator
¶ Bases:
object
Let \(G\) be an abelian group and suppose that \((g_0, \ldots, g_n)\) is a list of elements of \(G\), whose additive orders are equal to \(m_i\) and \(\sum_{i=0}^n x_i g_i = 0\) for \(x_i \in \ZZ_{m_i}\) for \(i \in \{0, \dots, n\}\) implies \(x_i=0\) for all \(i\).
This class implements an iterator over the \(\ZZ\)-submodule \(M = \{\sum_{i=0}^n x_i g_i\}\). If the independence condition from above is not fulfilled, we can still use this iterator to run over the elements. In this case the elements will occur multiple times.
Getting from one element of the submodule to another is performed by one single addition in \(G\).
INPUT:
basis
- the elements \((g_0, \ldots, g_n)\)order
(optional) - the additive_orders \(m_i\) of \(g_i\).coset_rep
(optional) – an element of g, if one aims to compute a coset of the \(\ZZ\)-submodule \(M\).immutable
(optional; default:False
) – set it toTrue
to return immutable elements. Setting this toTrue
makes sense if the elements are vectors. SeeFiniteFieldsubspace_iterator
for examples.
EXAMPLES:
sage: from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator sage: F.<x,y,z> = FreeAlgebra(GF(3),3) sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3]) sage: list(iter) [0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y] sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3], z) sage: list(iter) [z, x + z, 2*x + z, y + z, x + y + z, 2*x + y + z, 2*y + z, x + 2*y + z, 2*x + 2*y + z]