Cartesian Products

class sage.combinat.cartesian_product.CartesianProduct_iters(*iters)[source]

Bases: EnumeratedSetFromIterator

Cartesian product of finite sets.

This class will soon be deprecated (see Issue #18411 and Issue #19195). One should instead use the functorial construction cartesian_product. The main differences in behavior are:

  • construction: CartesianProduct takes as many argument as there are factors whereas cartesian_product takes a single list (or iterable) of factors;

  • representation of elements: elements are represented by plain Python list for CartesianProduct versus a custom element class for cartesian_product;

  • membership testing: because of the above, plain Python lists are not considered as elements of a cartesian_product.

All of these is illustrated in the examples below.

EXAMPLES:

sage: F1 = ['a', 'b']
sage: F2 = [1, 2, 3, 4]
sage: F3 = Permutations(3)
sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: C = CartesianProduct_iters(F1, F2, F3)
sage: c = cartesian_product([F1, F2, F3])

sage: type(C.an_element())
<class 'list'>
sage: type(c.an_element())
<class 'sage.sets.cartesian_product.CartesianProduct_with_category.element_class'>

sage: l = ['a', 1, Permutation([3,2,1])]
sage: l in C
True
sage: l in c
False
sage: elt = c(l)
sage: elt
('a', 1, [3, 2, 1])
sage: elt in c
True
sage: elt.parent() is c
True

>>> from sage.all import *
>>> F1 = ['a', 'b']
>>> F2 = [Integer(1), Integer(2), Integer(3), Integer(4)]
>>> F3 = Permutations(Integer(3))
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> C = CartesianProduct_iters(F1, F2, F3)
>>> c = cartesian_product([F1, F2, F3])

>>> type(C.an_element())
<class 'list'>
>>> type(c.an_element())
<class 'sage.sets.cartesian_product.CartesianProduct_with_category.element_class'>

>>> l = ['a', Integer(1), Permutation([Integer(3),Integer(2),Integer(1)])]
>>> l in C
True
>>> l in c
False
>>> elt = c(l)
>>> elt
('a', 1, [3, 2, 1])
>>> elt in c
True
>>> elt.parent() is c
True
cardinality()[source]

Return the number of elements in the Cartesian product of everything in *iters.

EXAMPLES:

sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: CartesianProduct_iters(range(2), range(3)).cardinality()
6
sage: CartesianProduct_iters(range(2), range(3)).cardinality()
6
sage: CartesianProduct_iters(range(2), range(3), range(4)).cardinality()
24

>>> from sage.all import *
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> CartesianProduct_iters(range(Integer(2)), range(Integer(3))).cardinality()
6
>>> CartesianProduct_iters(range(Integer(2)), range(Integer(3))).cardinality()
6
>>> CartesianProduct_iters(range(Integer(2)), range(Integer(3)), range(Integer(4))).cardinality()
24

This works correctly for infinite objects:

sage: CartesianProduct_iters(ZZ, QQ).cardinality()
+Infinity
sage: CartesianProduct_iters(ZZ, []).cardinality()
0

>>> from sage.all import *
>>> CartesianProduct_iters(ZZ, QQ).cardinality()
+Infinity
>>> CartesianProduct_iters(ZZ, []).cardinality()
0
is_finite()[source]

The Cartesian product is finite if all of its inputs are finite, or if any input is empty.

EXAMPLES:

sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: CartesianProduct_iters(ZZ, []).is_finite()
True
sage: CartesianProduct_iters(4,4).is_finite()
Traceback (most recent call last):
...
ValueError: unable to determine whether this product is finite

>>> from sage.all import *
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> CartesianProduct_iters(ZZ, []).is_finite()
True
>>> CartesianProduct_iters(Integer(4),Integer(4)).is_finite()
Traceback (most recent call last):
...
ValueError: unable to determine whether this product is finite
list()[source]

Return.

EXAMPLES:

sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: CartesianProduct_iters(range(3), range(3)).list()
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
sage: CartesianProduct_iters('dog', 'cat').list()
[['d', 'c'],
 ['d', 'a'],
 ['d', 't'],
 ['o', 'c'],
 ['o', 'a'],
 ['o', 't'],
 ['g', 'c'],
 ['g', 'a'],
 ['g', 't']]

>>> from sage.all import *
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> CartesianProduct_iters(range(Integer(3)), range(Integer(3))).list()
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
>>> CartesianProduct_iters('dog', 'cat').list()
[['d', 'c'],
 ['d', 'a'],
 ['d', 't'],
 ['o', 'c'],
 ['o', 'a'],
 ['o', 't'],
 ['g', 'c'],
 ['g', 'a'],
 ['g', 't']]
random_element()[source]

Return a random element from the Cartesian product of *iters.

EXAMPLES:

sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: c = CartesianProduct_iters('dog', 'cat').random_element()
sage: c in CartesianProduct_iters('dog', 'cat')
True

>>> from sage.all import *
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> c = CartesianProduct_iters('dog', 'cat').random_element()
>>> c in CartesianProduct_iters('dog', 'cat')
True
unrank(x)[source]

For finite Cartesian products, we can reduce unrank to the constituent iterators.

EXAMPLES:

sage: from sage.combinat.cartesian_product import CartesianProduct_iters
sage: C = CartesianProduct_iters(range(1000), range(1000), range(1000))
sage: C[238792368]
[238, 792, 368]

>>> from sage.all import *
>>> from sage.combinat.cartesian_product import CartesianProduct_iters
>>> C = CartesianProduct_iters(range(Integer(1000)), range(Integer(1000)), range(Integer(1000)))
>>> C[Integer(238792368)]
[238, 792, 368]

Check for Issue #15919:

sage: FF = IntegerModRing(29)
sage: C = CartesianProduct_iters(FF, FF, FF)
sage: C.unrank(0)
[0, 0, 0]

>>> from sage.all import *
>>> FF = IntegerModRing(Integer(29))
>>> C = CartesianProduct_iters(FF, FF, FF)
>>> C.unrank(Integer(0))
[0, 0, 0]