id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
15425 Cleanup cartesian products nthiery "Currently we have: {{{cartesian_product}}}, {{{CartesianProduct}}} and
{{{cartesian_product_iterator}}} for constructing cartesian products.
- {{{CartesianProduct}}} is an old simple parent that focuses on the
""enumerated sets"" aspect: providing counting and enumeration over
cartesian products of enumerated sets. It accepts any iterables as
input.
- {{{cartesian_product}}} is a ""functorial construction"". This means
that it uses the categories to endow the resulting parent with as
much structure as it can lift from the input. E.g. the cartesian
product of two monoids is a monoid.
- {{{cartesian_product_iterator}}} is just a function that provides an
iterator
To be done:
1. #18411: Make {{{CartesianProduct}}} an alias for {{{cartesian_product}}}, and possibly deprecated it. The missing features at this point are:
- Accepting any iterable as input. This probably requires turning
them into parents (e.g. with {{{FiniteEnumeratedSet}}}). The overhead
is probably negligible in most cases, but one would need to double
check that we don't have spots where {{{CartesianProduct}}} is used
intensively for very small calculations. #14224 can be closed once this is fixed.
- Some features of {{{CartesianProduct}}} still need to be lifted to
{{{Sets.Finite.CartesianProducts}}} or {{{EnumeratedSets.CartesianProducts}}}. The
`cardinality` and `is_finite` methods are taken care in #18290. Some other
are in #18411.
- #19195: Fix the use of `CartesianProduct` in `CombinatorialFreeModule`
2. Remove {{{cartesian_product_iterator}}} from the global name space, and deprecate it altogether if, after checking, it turns out to be really just a duplicated of {{{itertools.product}}}.
3. #16289: Fix bug in cartesian_product (reported by Vincent Delecroix in [https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M this thread]):
{{{
sage: C = cartesian_product([ZZ,ZZ])
...
AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
}}}
This is a regression that is caused by a small change introduced by
#12959 in {{{Sets.ParentMethods.CartesianProduct}}}:
{{{
return parents[0].__class__ -> return parents[0].__class__
}}}
I (Nicolas) take a double blame for it: I was reviewer of this ticket
and did not notice this chunk (or don't remember why it was
introduced), and I had not written an appropriate test in the first
place. So this needs to be fixed too.
4. #16269: Fix bug reported by Nathann Cohen in [https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J this thread]: when converting a
list to an element of a cartesian product:
{{{
sage: Z3 = IntegerModRing(3)
sage: C = cartesian_product([Z3,Z3])
sage: C([Z3(2),Z3(2)])^2
(1, 1)
sage: C([2,2])^2 # Ooops
(4, 4)
}}}
The fix would be convert the operands of the list into the respective
parents in
{{{sage.sets.cartesian_product.CartesianProduct._element_constructor}}}.
5. Fix mixed cartesian products with modules and non modules:
{{{
sage: A = AlgebrasWithBasis(QQ).example(); A.rename(""A"")
sage: cartesian_product([A, ZZ])
...
AttributeError: 'sage.rings.integer_ring.IntegerRing_class' object has no attribute 'basis'
}}}
This should instead detect that not all factors are modules, and
just use a plain cartesian product.
Also between modules on different ring, in particular #18309.
6. Fix cartesian products involving {{{NN}}}:
{{{
sage: cartesian_product([NN,NN])
170 from sage.structure.parent import Parent
--> 171 assert(all(isinstance(parent, Parent) for parent in parents))
172 # Should we pass a set of categories to reduce the cache size?
173 # But then this would impose that, for any constructor, the
AssertionError:
}}}
This is in fact a bug in the way {{{NN}}} is lazy imported in the global
name space:
{{{
sage: type(NN)
sage: isinstance(NN, Parent)
False
}}}
Things works if one forces the import of {{{NN}}}:
{{{
sage: NN = NonNegativeIntegers()
sage: cartesian_product([NN,NN])
The cartesian product of (Non negative integers, Non negative integers)
}}}
7. Make `_cartesian_product_of_elements` a public method?
8. Add a tutorial in `Sets.SubcategoryMethods.CartesianProducts`
describing the general scheme, possibly starting from the blurb there:
https://groups.google.com/d/msg/sage-combinat-devel/s_aPBD6BgOg/H1aJbCI1TYoJ
9. Tidy up the documentation of sage.sets.cartesian_products:
Return(s), the links to `Sets....` don't need to be prefixed with
the python module (Sets is found from the global name space), ...
10. #16269 and follow up #16405 (depended on #10963): make the
cartesian product of an additive magma into an additive magma, and
so on; implement {{{Distributive.CartesianProducts}}} so that a
cartesian product of rings is a ring.
" task new major sage-6.9 categories sage-combinat ncohen vdelecroix N/A