nthiery
commented
10 years ago Description changed:
---
+++
@@ -14,74 +14,80 @@
- `cartesian_product_iterator` is just a function that provides an
iterator
-`cartesian_product` is meant to subdue `CartesianProduct`. The
-missing features at this point are:
+To be done:
-- 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.
+#. Make `CartesianProduct` an alias for `cartesian_product`,
+ and possibly deprecated it.
- #14224 which can be closed once this is fixed.
+ The missing features at this point are:
-- Some features of CartesianProduct still need to be lifted to
- Sets.Finite.CartesianProducts or EnumeratedSets.CartesianProducts.
- For example, cardinality is currently calculated from the iterator (gasp):
+ - 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.
- ```
- sage: F = Permutations(10)
- sage: C = cartesian_product([F,F])
- sage: C.cardinality()
- *hangs forever*
- ```
+ #14224 can be closed once this is fixed.
-Once this is done, we can make CartesianProduct an alias for
-cartesian_product, and maybe deprecate it in the long run.
+ - Some features of CartesianProduct still need to be lifted to
+ Sets.Finite.CartesianProducts or EnumeratedSets.CartesianProducts.
+ For example, cardinality is currently calculated from the iterator (gasp):
-My 2 cents for cartesian_product_iterator: it should be removed from
-the global name space, and deprecated altogether if after checking it
-turns out to be really just a duplicated of itertools.product.
+ ```
+ sage: F = Permutations(10)
+ sage: C = cartesian_product([F,F])
+ sage: C.cardinality()
+ *hangs forever*
+ ```
-Another bug in cartesian_product (reported by Vincent Delecroix [1]):
+ Done by #16269/#10963 for cardinality and `__iter__`. Needs
+ double checking for the infinite cases.
-```
-sage: C = cartesian_product([ZZ,ZZ])
-...
-AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
-```
+#. 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.
-This is a regression that is caused by a small change introduced by
-#12959 in Sets.ParentMethods.CartesianProduct:
+#. Fix bug in cartesian_product (reported by Vincent Delecroix [1]):
-```
- return parents[0].__class__ -> return parents[0].__class__
-```
+ ```
+ sage: C = cartesian_product([ZZ,ZZ])
+ ...
+ AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
+ ```
-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.
+ This is a regression that is caused by a small change introduced by
+ #12959 in Sets.ParentMethods.CartesianProduct:
-Yet another bug reported by Nathann Cohen [2]: when converting a list
-to an element of a cartesian product:
+ ```
+ return parents[0].__class__ -> return parents[0].__class__
+ ```
-```
-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)
-```
+ 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.
-The fix would be convert the operands of the list into the respective
-parents in
-`sage.sets.cartesian_product.CartesianProduct._element_constructor`.
+#. #16269: Fix bug reported by Nathann Cohen [2]: when converting a
+ list to an element of a cartesian product:
-Many features could be further added, like for example making the
-cartesian product of an additive magma into an additive magma and so
-on. This can go in this ticket or in later tickets.
+ ```
+ 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`.
+
+#. Many features could be further added, like for example making the
+ cartesian product of an additive magma into an additive magma and
+ so on. A good step was done with #16269. Another step needs to be
+ done after #10963 to ventilate the features in the appropriate
+ axiom categories.
[1] https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M
[2] https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J
videlec
6bdad4c1-1e26-4f2f-a442-a01a2292c181
fchapoton
mkoeppe
Currently we have:
cartesian_product,CartesianProductandcartesian_product_iteratorfor constructing cartesian products.CartesianProductis 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_productis 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_iteratoris just a function that provides an iteratorTo be done:
18411: Make
CartesianProductan alias forcartesian_product, and possibly deprecated it. The missing features at this point are:FiniteEnumeratedSet). The overhead is probably negligible in most cases, but one would need to double check that we don't have spots whereCartesianProductis used intensively for very small calculations. #14224 can be closed once this is fixed.CartesianProductstill need to be lifted toSets.Finite.CartesianProductsorEnumeratedSets.CartesianProducts. Thecardinalityandis_finitemethods are taken care in #18290. Some other are in #18411.19195: Fix the use of
CartesianProductinCombinatorialFreeModule34337: Remove
cartesian_product_iteratorfrom the global name space, and deprecate it altogether if, after checking, it turns out to be really just a duplicated ofitertools.product.16289: Fix bug in cartesian_product (reported by Vincent Delecroix in this thread):
This is a regression that is caused by a small change introduced by
12959 in
Sets.ParentMethods.CartesianProduct: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.
16269: Fix bug reported by Nathann Cohen in this thread: when converting a
list to an element of a cartesian product:
The fix would be convert the operands of the list into the respective parents in
sage.sets.cartesian_product.CartesianProduct._element_constructor.Fix mixed cartesian products with modules and non modules:
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.
34652: Fix cartesian products involving
NN:This is in fact a bug in the way
NNis lazy imported in the global name space:Things works if one forces the import of
NN:Make
_cartesian_product_of_elementsa public method?Add a tutorial in
Sets.SubcategoryMethods.CartesianProductsdescribing the general scheme, possibly starting from the blurb there: https://groups.google.com/d/msg/sage-combinat-devel/s_aPBD6BgOg/H1aJbCI1TYoJTidy 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), ...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.CartesianProductsso that a cartesian product of rings is a ring.CC: @sagetrac-sage-combinat @nathanncohen @videlec @tscrim
Component: categories
Issue created by migration from https://trac.sagemath.org/ticket/15425