Multidimensional enumeration#

AUTHORS:

  • Joel B. Mohler (2006-10-12)

  • William Stein (2006-07-19)

  • Jon Hanke

sage.misc.mrange.cantor_product(*args, **kwds)[source]#

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 repeated repeat 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)]

>>> from sage.all import *
>>> from sage.misc.mrange import cantor_product
>>> list(cantor_product([Integer(0), Integer(1)], repeat=Integer(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)]
>>> list(cantor_product([Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(2), Integer(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)]

>>> from sage.all import *
>>> from itertools import islice
>>> list(islice(cantor_product(ZZ, QQ), 14))
 [(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)[source]#

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

>>> from sage.all import *
>>> list(cartesian_product_iterator([[Integer(1),Integer(2)], ['a','b']]))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
>>> list(cartesian_product_iterator([]))
[()]
sage.misc.mrange.mrange(sizes, typ=<class 'list'>)[source]#

Return the multirange list with given sizes and type.

This is the list version of xmrange. Use xmrange 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 integers

  • typ – (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]

>>> from sage.all import *
>>> mrange([Integer(3),Integer(2)])
[[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]
>>> mrange([Integer(3),Integer(2)], tuple)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
>>> mrange([Integer(3),Integer(2)], sum)
[0, 1, 1, 2, 2, 3]

Examples that illustrate empty multi-ranges:

sage: mrange([5,3,-2])
[]
sage: mrange([5,3,0])
[]

>>> from sage.all import *
>>> mrange([Integer(5),Integer(3),-Integer(2)])
[]
>>> mrange([Integer(5),Integer(3),Integer(0)])
[]

This example is not empty, and should not be. See Issue #6561.

sage: mrange([])
[[]]

>>> from sage.all import *
>>> mrange([])
[[]]

AUTHORS:

  • Jon Hanke

  • William Stein

sage.misc.mrange.mrange_iter(iter_list, typ=<class 'list'>)[source]#

Return the multirange list derived from the given list of iterators.

This is the list version of xmrange_iter(). Use xmrange_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 iterables

  • typ – (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]

>>> from sage.all import *
>>> mrange_iter([range(Integer(3)),[Integer(0),Integer(2)]])
[[0, 0], [0, 2], [1, 0], [1, 2], [2, 0], [2, 2]]
>>> mrange_iter([['Monty','Flying'],['Python','Circus']], tuple)
[('Monty', 'Python'), ('Monty', 'Circus'), ('Flying', 'Python'), ('Flying', 'Circus')]
>>> mrange_iter([[Integer(2),Integer(3),Integer(5),Integer(7)],[Integer(1),Integer(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)])
[]

>>> from sage.all import *
>>> mrange_iter([range(Integer(5)),range(Integer(3)),range(Integer(0))])
[]
>>> mrange_iter([range(Integer(5)), range(Integer(3)), range(-Integer(2))])
[]

This example is not empty, and should not be. See Issue #6561.

sage: mrange_iter([])
[[]]

>>> from sage.all import *
>>> mrange_iter([])
[[]]

AUTHORS:

  • Joel B. Mohler

class sage.misc.mrange.xmrange(sizes, typ=<class 'list'>)[source]#

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 integers

  • 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([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)

>>> from sage.all import *
>>> z = xmrange([Integer(3),Integer(2)]);z
xmrange([3, 2])
>>> z = xmrange([Integer(3),Integer(2)], tuple);z
xmrange([3, 2], <... 'tuple'>)
>>> 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)]

>>> from sage.all import *
>>> list(xmrange([Integer(3),Integer(2)]))
[[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]
>>> list(xmrange([Integer(3),Integer(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]

>>> from sage.all import *
>>> list(xmrange([Integer(3),Integer(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]

>>> from sage.all import *
>>> list(xmrange([Integer(3),Integer(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]))
[]

>>> from sage.all import *
>>> list(xmrange([Integer(5),Integer(3),-Integer(2)]))
[]
>>> list(xmrange([Integer(5),Integer(3),Integer(0)]))
[]

This example is not empty, and should not be. See Issue #6561.

sage: list(xmrange([]))
[[]]

>>> from sage.all import *
>>> 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')

>>> from sage.all import *
>>> X = ['red', 'apple', Integer(389)]
>>> Y = ['orange', 'horse']
>>> 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'>)[source]#

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 (possibly

    lists)

  • 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)

>>> from sage.all import *
>>> z = xmrange_iter([list(range(Integer(3))),list(range(Integer(2)))], tuple);z
xmrange_iter([[0, 1, 2], [0, 1]], <... 'tuple'>)
>>> 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)]

>>> from sage.all import *
>>> list(xmrange_iter([range(Integer(3)),range(Integer(2))]))
[[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]
>>> list(xmrange_iter([range(Integer(3)),range(Integer(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]

>>> from sage.all import *
>>> list(xmrange_iter([range(Integer(3)),range(Integer(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]

>>> from sage.all import *
>>> list(xmrange_iter([range(Integer(3)),range(Integer(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)]))
[]

>>> from sage.all import *
>>> list(xmrange_iter([range(Integer(5)),range(Integer(3)),range(-Integer(2))]))
[]
>>> list(xmrange_iter([range(Integer(5)),range(Integer(3)),range(Integer(0))]))
[]

This example is not empty, and should not be. See Issue #6561.

sage: list(xmrange_iter([]))
[[]]

>>> from sage.all import *
>>> 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')

>>> from sage.all import *
>>> X = ['red', 'apple', Integer(389)]
>>> Y = ['orange', 'horse']
>>> 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()[source]#

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

>>> from sage.all import *
>>> C = cartesian_product_iterator([range(Integer(3)),range(Integer(4))])
>>> C.cardinality()
12
>>> C = cartesian_product_iterator([ZZ,QQ])
>>> C.cardinality()
+Infinity
>>> C = cartesian_product_iterator([ZZ,[]])
>>> C.cardinality()
0