Multidimensional enumeration¶
AUTHORS:
Joel B. Mohler (2006-10-12)
William Stein (2006-07-19)
Jon Hanke
-
sage.misc.mrange.
cantor_product
(*args, **kwds)¶ Return an iterator over the product of the inputs along the diagonals a la Cantor pairing.
INPUT:
a certain number of iterables
repeat
– an optional integer. If it is provided, the input is repeatedrepeat
times.
Other keyword arguments are passed to
sage.combinat.integer_lists.invlex.IntegerListsLex
.EXAMPLES:
sage: from sage.misc.mrange import cantor_product sage: list(cantor_product([0, 1], repeat=3)) [(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1)] sage: list(cantor_product([0, 1], [0, 1, 2, 3])) [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2), (0, 3), (1, 3)]
Infinite iterators are valid input as well:
sage: from itertools import islice sage: list(islice(cantor_product(ZZ, QQ), 14r)) [(0, 0), (1, 0), (0, 1), (-1, 0), (1, 1), (0, -1), (2, 0), (-1, 1), (1, -1), (0, 1/2), (-2, 0), (2, 1), (-1, -1), (1, 1/2)]
-
sage.misc.mrange.
cartesian_product_iterator
(X)¶ Iterate over the Cartesian product.
INPUT:
X
- list or tuple of lists
OUTPUT: iterator over the Cartesian product of the elements of X
EXAMPLES:
sage: list(cartesian_product_iterator([[1,2], ['a','b']])) [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')] sage: list(cartesian_product_iterator([])) [()]
-
sage.misc.mrange.
mrange
(sizes, typ=<class 'list'>)¶ Return the multirange list with given sizes and type.
This is the list version of
xmrange
. Usexmrange
for the iterator.More precisely, return the iterator over all objects of type typ of n-tuples of Python ints with entries between 0 and the integers in the sizes list. The iterator is empty if sizes is empty or contains any non-positive integer.
INPUT:
sizes
- a list of nonnegative integerstyp
- (default: list) a type or class; more generally, something that can be called with a list as input.
OUTPUT: a list
EXAMPLES:
sage: mrange([3,2]) [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]] sage: mrange([3,2], tuple) [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)] sage: mrange([3,2], sum) [0, 1, 1, 2, 2, 3]
Examples that illustrate empty multi-ranges:
sage: mrange([5,3,-2]) [] sage: mrange([5,3,0]) []
This example is not empty, and should not be. See trac ticket #6561.
sage: mrange([]) [[]]
AUTHORS:
Jon Hanke
William Stein
-
sage.misc.mrange.
mrange_iter
(iter_list, typ=<class 'list'>)¶ Return the multirange list derived from the given list of iterators.
This is the list version of
xmrange_iter()
. Usexmrange_iter
for the iterator.More precisely, return the iterator over all objects of type
typ
of n-tuples of Python ints with entries between 0 and the integers in the sizes list. The iterator is empty if sizes is empty or contains any non-positive integer.INPUT:
iter_list
- a finite iterable of finite iterablestyp
- (default: list) a type or class; more generally, something that can be called with a list as input.
OUTPUT: a list
EXAMPLES:
sage: mrange_iter([range(3),[0,2]]) [[0, 0], [0, 2], [1, 0], [1, 2], [2, 0], [2, 2]] sage: mrange_iter([['Monty','Flying'],['Python','Circus']], tuple) [('Monty', 'Python'), ('Monty', 'Circus'), ('Flying', 'Python'), ('Flying', 'Circus')] sage: mrange_iter([[2,3,5,7],[1,2]], sum) [3, 4, 4, 5, 6, 7, 8, 9]
Examples that illustrate empty multi-ranges:
sage: mrange_iter([range(5),range(3),range(0)]) [] sage: mrange_iter([range(5), range(3), range(-2)]) []
This example is not empty, and should not be. See trac ticket #6561.
sage: mrange_iter([]) [[]]
AUTHORS:
Joel B. Mohler
-
class
sage.misc.mrange.
xmrange
(sizes, typ=<class 'list'>)¶ Bases:
object
Return the multirange iterate with given sizes and type.
More precisely, return the iterator over all objects of type typ of n-tuples of Python ints with entries between 0 and the integers in the sizes list. The iterator is empty if sizes is empty or contains any non-positive integer.
Use mrange for the non-iterator form.
INPUT:
sizes
- a list of nonnegative integerstyp
- (default: list) a type or class; more generally, something that can be called with a list as input.
OUTPUT: a generator
EXAMPLES: We create multi-range iterators, print them and also iterate through a tuple version.
sage: z = xmrange([3,2]);z xmrange([3, 2]) sage: z = xmrange([3,2], tuple);z xmrange([3, 2], <... 'tuple'>) sage: for a in z: ....: print(a) (0, 0) (0, 1) (1, 0) (1, 1) (2, 0) (2, 1)
We illustrate a few more iterations.
sage: list(xmrange([3,2])) [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]] sage: list(xmrange([3,2], tuple)) [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
Here we compute the sum of each element of the multi-range iterator:
sage: list(xmrange([3,2], sum)) [0, 1, 1, 2, 2, 3]
Next we compute the product:
sage: list(xmrange([3,2], prod)) [0, 0, 0, 1, 0, 2]
Examples that illustrate empty multi-ranges.
sage: list(xmrange([5,3,-2])) [] sage: list(xmrange([5,3,0])) []
This example is not empty, and should not be. See trac ticket #6561.
sage: list(xmrange([])) [[]]
We use a multi-range iterator to iterate through the Cartesian product of sets.
sage: X = ['red', 'apple', 389] sage: Y = ['orange', 'horse'] sage: for i,j in xmrange([len(X), len(Y)]): ....: print((X[i], Y[j])) ('red', 'orange') ('red', 'horse') ('apple', 'orange') ('apple', 'horse') (389, 'orange') (389, 'horse')
AUTHORS:
Jon Hanke
William Stein
-
class
sage.misc.mrange.
xmrange_iter
(iter_list, typ=<class 'list'>)¶ Bases:
object
Return the multirange iterate derived from the given iterators and type.
Note
This basically gives you the Cartesian product of sets.
More precisely, return the iterator over all objects of type typ of n-tuples of Python ints with entries between 0 and the integers in the sizes list. The iterator is empty if sizes is empty or contains any non-positive integer.
Use
mrange_iter()
for the non-iterator form.INPUT:
iter_list
- a list of objects usable as iterators (possiblylists)
typ
- (default: list) a type or class; more generally,something that can be called with a list as input.
OUTPUT: a generator
EXAMPLES: We create multi-range iterators, print them and also iterate through a tuple version.
sage: z = xmrange_iter([list(range(3)),list(range(2))], tuple);z xmrange_iter([[0, 1, 2], [0, 1]], <... 'tuple'>) sage: for a in z: ....: print(a) (0, 0) (0, 1) (1, 0) (1, 1) (2, 0) (2, 1)
We illustrate a few more iterations.
sage: list(xmrange_iter([range(3),range(2)])) [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]] sage: list(xmrange_iter([range(3),range(2)], tuple)) [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
Here we compute the sum of each element of the multi-range iterator:
sage: list(xmrange_iter([range(3),range(2)], sum)) [0, 1, 1, 2, 2, 3]
Next we compute the product:
sage: list(xmrange_iter([range(3),range(2)], prod)) [0, 0, 0, 1, 0, 2]
Examples that illustrate empty multi-ranges.
sage: list(xmrange_iter([range(5),range(3),range(-2)])) [] sage: list(xmrange_iter([range(5),range(3),range(0)])) []
This example is not empty, and should not be. See trac ticket #6561.
sage: list(xmrange_iter([])) [[]]
We use a multi-range iterator to iterate through the Cartesian product of sets.
sage: X = ['red', 'apple', 389] sage: Y = ['orange', 'horse'] sage: for i,j in xmrange_iter([X, Y], tuple): ....: print((i, j)) ('red', 'orange') ('red', 'horse') ('apple', 'orange') ('apple', 'horse') (389, 'orange') (389, 'horse')
AUTHORS:
Joel B. Mohler
-
cardinality
()¶ Return the cardinality of this iterator.
EXAMPLES:
sage: C = cartesian_product_iterator([range(3),range(4)]) sage: C.cardinality() 12 sage: C = cartesian_product_iterator([ZZ,QQ]) sage: C.cardinality() +Infinity sage: C = cartesian_product_iterator([ZZ,[]]) sage: C.cardinality() 0