Opened 9 years ago
Last modified 7 years ago
#15425 new task
Cleanup cartesian products
Reported by: | nthiery | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.9 |
Component: | categories | Keywords: | |
Cc: | sage-combinat, ncohen, vdelecroix | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
- #18411: Make
CartesianProduct
an alias forcartesian_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 whereCartesianProduct
is used intensively for very small calculations. #14224 can be closed once this is fixed. - Some features of
CartesianProduct
still need to be lifted toSets.Finite.CartesianProducts
orEnumeratedSets.CartesianProducts
. Thecardinality
andis_finite
methods are taken care in #18290. Some other are in #18411. - #19195: Fix the use of
CartesianProduct
inCombinatorialFreeModule
- Accepting any iterable as input. This probably requires turning
them into parents (e.g. with
- 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 ofitertools.product
.
- #16289: Fix bug in cartesian_product (reported by Vincent Delecroix in 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.
- #16269: Fix bug reported by Nathann Cohen in 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
.
- 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.
- 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) <type 'sage.misc.lazy_import.LazyImport'> sage: isinstance(NN, Parent) FalseThings 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)
- Make
_cartesian_product_of_elements
a public method?
- 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
- 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), ...
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.
Change History (17)
comment:1 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Cc ncohen vdelecroix added
- Description modified (diff)
- Type changed from defect to task
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Description modified (diff)
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 8 years ago by
I think it is bad to hide
cartesian_product_iterator
as the object is very nice. We should advertise theproduct
fromitertools
somewhere.
We could mention it in the docstring of cartesian_product
. "If you just want to list the elements, use itertools.product as it is much faster" ?
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Replying to ncohen:
I think it is bad to hide
cartesian_product_iterator
as the object is very nice. We should advertise theproduct
fromitertools
somewhere.We could mention it in the docstring of
cartesian_product
. "If you just want to list the elements, use itertools.product as it is much faster" ?
Sounds good to me, with 'list -> iterate through'
comment:7 Changed 8 years ago by
- Description modified (diff)
comment:8 Changed 8 years ago by
- Description modified (diff)
comment:9 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:10 Changed 8 years ago by
- Description modified (diff)
comment:11 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:12 Changed 7 years ago by
- Description modified (diff)
comment:13 Changed 7 years ago by
Hello,
I think that we should get rid of _cartesian_product_of_elements
. If we want speed we can either:
- add an argument
coerce
to the_element_constructor_
- use directly
element_class
Vincent
comment:14 Changed 7 years ago by
Shouldn't the two following commands give the same answer
sage: ZZ**2 Ambient free module of rank 2 over the principal ideal domain Integer Ring sage: cartesian_product([ZZ,ZZ]) The cartesian product of (Integer Ring, Integer Ring)
comment:15 Changed 7 years ago by
- Description modified (diff)
comment:16 Changed 7 years ago by
- Description modified (diff)
comment:17 Changed 7 years ago by
- Description modified (diff)
- Milestone changed from sage-6.4 to sage-6.9
Hello,
+1 on that ticket!
I cleaned a bit the description.
I think it is bad to hide
cartesian_product_iterator
as the object is very nice. We should advertise theproduct
fromitertools
somewhere.Vincent