Opened 5 years ago
Closed 4 years ago
#18411 closed enhancement (fixed)
get rid of CartesianProduct
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.10 
Component:  combinatorics  Keywords:  
Cc:  nthiery, ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nicolas M. Thiéry 
Report Upstream:  N/A  Work issues:  
Branch:  6e27dde (Commits)  Commit:  6e27ddedfb0e8322914e6fd036dbe5b3fef6f996 
Dependencies:  #17411  Stopgaps: 
Description (last modified by )
The features of sage.combinat.cartesian_product.CartesianProduct
are now completely integrated into the category framework (see #18290). We remove all occurrences of CartesianProduct
to either cartesian_product
or itertools.product
. We deprecate the CartesianProduct
from sage.combinat.cartesian_product
.
In order to support all features of the old class we also:
 move the
__iter__
fromEnumeratedSets.CartesianProducts.ParentMethods
toSets.CartesianProducts.ParentMethods
 allows
cartesian_product
to be called withlist
,tuple
,set
,frozenset
 make
cartesian_product([])
works  introduce a function
some_tuples
insage.misc.misc
that is intensively used in the testing framework (and incidentally speed up some doc test)  refine the category of
Set([1,2,3])
to be finite  implement a (very naive)
random_element
forSet([1,2,3])
 implement a (naive) hash for
EnumeratedSetFromIterator
see also : #15425, #19195 one that can be closed as duplicate: #14224, #19192
Change History (70)
comment:1 Changed 5 years ago by
 Dependencies set to #18290, #12955
 Description modified (diff)
comment:2 Changed 4 years ago by
 Branch set to public/18411
comment:3 Changed 4 years ago by
 Commit set to e703eb4437d7b5bec7abc392e2fdfa534c86b704
comment:4 Changed 4 years ago by
 Commit changed from e703eb4437d7b5bec7abc392e2fdfa534c86b704 to 10df21841341b144bff58847011bae02cd852be9
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
635279f  Trac 18411: a bounded_number_of_tuples function

1b60903  Trac 18411: remove occurrences of CartesianProduct

bec57ae  Trac 18411: cartesian_product works with tuple/list/set/frozenset

7dbb663  Trac 18411: move iteration of cartesian products to Sets

4fbb4ae  Trac 18411: refine category of Set(...)

10df218  Trac 18411: fix combinat tutorial

comment:5 Changed 4 years ago by
 Dependencies #18290, #12955 deleted
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Get rid of sage.combinat.cartesian_product to remove some CartesianProduct usages
comment:6 Changed 4 years ago by
 Commit changed from 10df21841341b144bff58847011bae02cd852be9 to 57b82e3e3fdc7a4d07d0fe4d248f0c99557ce4f0
Branch pushed to git repo; I updated commit sha1. New commits:
57b82e3  trax #18411 fixing a typo and doctest continuation

comment:7 Changed 4 years ago by
Thanks Frédéric for fixing a doctest. Though, I do not see the point of modifying src/sage/rings/quotient_ring.py
. This file is completely unrelated to this ticket.
comment:8 Changed 4 years ago by
 Commit changed from 57b82e3e3fdc7a4d07d0fe4d248f0c99557ce4f0 to a640c244695188ec1c8bbec68b114f184baf1660
Branch pushed to git repo; I updated commit sha1. New commits:
a640c24  trac #18411 fixing some doctests

comment:9 Changed 4 years ago by
 Commit changed from a640c244695188ec1c8bbec68b114f184baf1660 to 3cc80709f3285c6fa012475681a6a74fdc0f4bf3
comment:10 Changed 4 years ago by
Hi Frédéric,
This was clearly not the way to fix composition_signed.py
. I removed this change from your commit. The rest of my commits should fix all issues with timed out testing (ie root system and padic) as well as the issue with tableau tuples.
Vincent
comment:11 Changed 4 years ago by
 Commit changed from 3cc80709f3285c6fa012475681a6a74fdc0f4bf3 to 70949c7a0b4206ce99e834f09f488bd682f9ca1c
Branch pushed to git repo; I updated commit sha1. New commits:
70949c7  Trac 18411: fix two doctests

comment:12 Changed 4 years ago by
 Commit changed from 70949c7a0b4206ce99e834f09f488bd682f9ca1c to 9beb0234950b59a7f755c05753e55f0c8637d454
Branch pushed to git repo; I updated commit sha1. New commits:
9beb023  Trac 18411: bound number of tests for Domains

comment:13 Changed 4 years ago by
 Description modified (diff)
comment:14 Changed 4 years ago by
 Commit changed from 9beb0234950b59a7f755c05753e55f0c8637d454 to 65808258b9bf22e5b7d6bb1543f7e2ee30634337
Branch pushed to git repo; I updated commit sha1. New commits:
6580825  Trac 18411: fix is_empty

comment:15 Changed 4 years ago by
The only failing doctest is fine when run independently... I am not sure what may have happend.
Vincent
comment:16 Changed 4 years ago by
 Commit changed from 65808258b9bf22e5b7d6bb1543f7e2ee30634337 to 8a5ca0185dc3d46b7c62429b3d60ccccb485c0c4
comment:17 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
 Summary changed from remove some CartesianProduct usages to get rid of CartesianProduct
comment:18 Changed 4 years ago by
I was worried with CombinatorialFreeModule
but it went smoothly. I just need to add a commit for the deprecation!
comment:19 Changed 4 years ago by
 Commit changed from 8a5ca0185dc3d46b7c62429b3d60ccccb485c0c4 to 4eacb2236a6f6d950bc3a0b0a4fb5bf038113a5c
comment:20 Changed 4 years ago by
 Description modified (diff)
comment:21 Changed 4 years ago by
 Description modified (diff)
comment:22 Changed 4 years ago by
Annoying bug:
sage: F = FiniteEnumeratedSet([int(1), int(2)]) sage: F(1) Traceback (most recent call last): ... TypeError: Cannot convert int to sage.structure.element.Element
And the following is also a bug IMHO
sage: FiniteEnumeratedSet([1,2]) is FiniteEnumeratedSet([int(1),int(2)]) True
comment:23 Changed 4 years ago by
 Commit changed from 4eacb2236a6f6d950bc3a0b0a4fb5bf038113a5c to 9f29074cb9a30ee194affe77ed5b7a28f9318df1
comment:24 Changed 4 years ago by
I got into troubles. Combinatorial free modules are too laxist and you discover mistakes only very lately... in the following an element g
is built
sage: M = SchurTensorModule(QQ, 2, 2) sage: A = M._schur sage: f = M.basis()[(1,1)] sage: e = A.basis().values()[0] sage: g = e*f
but it is not valid in the sense that the keys do not correspond to the basis
sage: map(type, g.monomial_coefficients().keys()) [<type 'tuple'>] sage: g.parent().basis().keys() The cartesian product of ({1, 2}, {1, 2})
And hence you silently got
sage: g.to_vector() (0, 0, 0, 0)
comment:25 Changed 4 years ago by
 Commit changed from 9f29074cb9a30ee194affe77ed5b7a28f9318df1 to 321067f0c83cdb19e3b3e52ac215511f9ebf620a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d0f900a  Trac 18411: remove two final occurrences

8819c3e  Trac 18411: hash for EnumeratedSetFromIterator

4c50a1c  Trac 18411: more explicit call in CombinatorialFreeModule

321067f  Trac 18411: deprecate CartesianProduct

comment:26 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
All right, my solution is to not use cartesian_product
in combinatorial free module and postponed this step to #19195. Needs review again.
Vincent
comment:27 Changed 4 years ago by
Patchbot's green light ;)
comment:28 Changed 4 years ago by
 Commit changed from 321067f0c83cdb19e3b3e52ac215511f9ebf620a to c2eeac83b37d9de3a547001fd704a1fb089c626c
Branch pushed to git repo; I updated commit sha1. New commits:
c2eeac8  Trac 18411: removed unused import

comment:29 Changed 4 years ago by
 Commit changed from c2eeac83b37d9de3a547001fd704a1fb089c626c to e7a2ff2e36fe378e05f4cb14adb4999c579b11ec
comment:30 Changed 4 years ago by
 Reviewers set to Nicolas Thiéry
I just implemented the changes requested By Nicolas Thiéry while we discussed on phone.
comment:31 Changed 4 years ago by
 Commit changed from e7a2ff2e36fe378e05f4cb14adb4999c579b11ec to ca0a9077452a1d127019c5aa1d9a0b9810e3df1b
Branch pushed to git repo; I updated commit sha1. New commits:
3661ec0  Trac 18411: more explicit error catch in sets_cat

7d12709  Trac 18411: composition: FiniteEnumeratedSet instead of Set

35b76c6  Trac 18411: simpler code in root_lattice_realizations.py

643e2f7  Trac 18411: restore some tests in family.py

6f7b379  Trac 18411: use itertools.product instead of product

2741384  Trac 18411: small edits in combinat/tutorial.py

ca0a907  Trac 18411: explanations about the transition

comment:32 Changed 4 years ago by
 Commit changed from ca0a9077452a1d127019c5aa1d9a0b9810e3df1b to 34a392fcf66d3ebc2679403970009af5d0d4e3a5
comment:33 Changed 4 years ago by
 Description modified (diff)
 Milestone changed from sage6.7 to sage6.9
comment:34 Changed 4 years ago by
 Commit changed from 34a392fcf66d3ebc2679403970009af5d0d4e3a5 to 07cc001e5c45b27a68088d175699732847adcc63
Branch pushed to git repo; I updated commit sha1. New commits:
07cc001  18411: Fixed unused import

comment:35 Changed 4 years ago by
 Commit changed from 07cc001e5c45b27a68088d175699732847adcc63 to 7c103df59914913d77102a559686d932d1918f1d
Branch pushed to git repo; I updated commit sha1. New commits:
7c103df  18411: cleanup spacing for optional arguments

comment:36 Changed 4 years ago by
 Commit changed from 7c103df59914913d77102a559686d932d1918f1d to a35ef8a704cc966a3a118c84b50a46e3cd6f6245
Branch pushed to git repo; I updated commit sha1. New commits:
a35ef8a  18411: proofreading

comment:37 Changed 4 years ago by
 Commit changed from a35ef8a704cc966a3a118c84b50a46e3cd6f6245 to 22f8b77a3cc2223863396f8d422fbbeec51d1656
Branch pushed to git repo; I updated commit sha1. New commits:
22f8b77  18411: proofreading

comment:38 Changed 4 years ago by
Here is a trace of the non trivial points we discussed privately with Vincent:
 enumerated_set_from_iterator: do we want instead to start filling
the cache in case it does not exist yet?
Nope. The cache might be *never* used in that class. And when it exists it is automatically filled since it is a lazy_list.
Oh, I had not noticed that, in EnumeratedSetFromIterator?, the existence of the cache was decided upon construction. +1 then.
 Why moving iter from EnumeratedSets?.CartesianProducts? to
Sets.CartesianProducts??
Because otherwise there are some failing doctests. For example
Set([1,2,3])
is iterable but the following was not
cartesian_product([Set(1,2,3), Set([1,2,3])])
The fact that something is iterable does not necessarily mean that it belongs to EnumeratedSet?. At least for me and the current class FiniteEnumeratedSet?, the enumerated set {1, 2, 3} is not equal to the enumerated set {3, 2, 1}. But they are equal as sets. And the set {1, 2, 3} should be iterable.
I see your point. Yet this is annoying; where do we want to put the exact limit between Set and EnumeratedSet?? Where should, e.g. features like cardinality_from_iterator live?
Hmm, I am not sure what to do here.
Right. My main motivation was to fix some doctests were previous code expected that the result was iterable. I do not exactly remind where it was.
Would it make sense to put it in Sets.Finite.CartesianProduct
, given
that it only works in the finite case?
The iterator is mandatory for cardinality_from_iterator, as it is not for Sets I would not put there.
Yeah, that's a good point.
 Do we want to systematically use itertools.product when in some
cases it's memory complexity is not as good as what we can do when we have iterables and not iterators as input?
Clearly not. But we are lacking something better. Once the list is expanded, you can not beat itertools. So in most cases, it is what you want since the size of factors is small compared to the size of the product.
 Sets 2034: is_empty:  don't catch all exceptions  is it about
parents not implementing is_empty, or about returning Unknown or raising an exception? In which case we should specify that exception and only catch that one.
done
 CartesianProduct_iters: Make the difference with cartesian_product
more explicit and add a link?
done
 Compositions: return FiniteEnumeratedSet?([self])
done
or make cartesian_product() return FiniteEnumeratedSet?([xxx]) or Set([xxx]) where xxx is the trivial tuple.
This is not a good idea. The interface should be uniform when you do elt[i] to access the ith cartesian projection.
 partition_tuple: could there not be other combinations, like (())?
I did not found any. The empty tuple comes from the iteration with product.
 root_lattice_realization: is the conversion to FiniteEnumeratedSet?
still necessary?
C = cartesian_product([PositiveIntegers?(), FiniteEnumeratedSet?(Q.roots())])
If so, should instead cartesian_product do more input tidying work?
Indeed, it is not. done.
 sets.family: maybe that test was about checking that things work
when a parent C is just in EnumeratedSets? but C.cardinality() == infinity
I reintroduced the test using cartesian_product instead of CartesianProduct?
... about
cartesian_product()
...So what about returning:
sage: from sage.sets.cartesian_product import CartesianProduct? sage: CartesianProduct?((), Sets().CartesianProducts?()) The cartesian product of ()
I vaguely remember we discussed this at some point, but don't remember what the outcome was. Of course if the user did not specify a category to cartesian_product(), we don't quite know what's the category he expects, but Sets().CartesianProducts?() sounds like a reasonable starting point.
I also remember that we discussed it. And indeed, for the sake of backward compatibility it needs to be done in that ticket... we had
sage: CartesianProduct?() Cartesian product of sage: CartesianProduct?().cardinality() 1 sage: CartesianProduct?().an_element() []
There is an other commit for that.
Thanks!
I made some minor review changes. Since the spacing commit for the tutorial was going the wrong way w.r.t. Python's convention, I allowed myself to revert it, and actually fix accordingly the surrounding lines (which I had written incorrectly a couple years ago). I hope that's ok.
Up to the final position of the __iter__
method which I am not yet
quite comfortable with, I am happy with the current state.
Anyone a point of view on this final sticking point?
Cheers,
Nicolas
comment:39 followup: ↓ 40 Changed 4 years ago by
If we switch back, only the following fails (from sage.combinat.tutorial
):
sage: Suits = Set(["Hearts", "Diamonds", "Spades", "Clubs"]) sage: Values = Set([2, 3, 4, 5, 6, 7, 8, 9, 10, ....: "Jack", "Queen", "King", "Ace"]) sage: Cards = cartesian_product([Values, Suits]) sage: Hands = Subsets(Cards, 5) Traceback (most recent call last): ... AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'
and the reason is because you can not do the list of Cards
...
sage: list(Cards) Traceback (most recent call last): ... AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'
There are of course other ways to fix it, but I found that it was the simplest. Using FiniteEnumeratedSet
instead of Set
in the tutorial seems unnatural to me since you want to keep it as simple as possible...
Vincent
comment:40 in reply to: ↑ 39 ; followup: ↓ 41 Changed 4 years ago by
Replying to vdelecroix:
If we switch back, only the following fails (from
sage.combinat.tutorial
):sage: Suits = Set(["Hearts", "Diamonds", "Spades", "Clubs"]) sage: Values = Set([2, 3, 4, 5, 6, 7, 8, 9, 10, ....: "Jack", "Queen", "King", "Ace"]) sage: Cards = cartesian_product([Values, Suits]) sage: Hands = Subsets(Cards, 5) Traceback (most recent call last): ... AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'and the reason is because you can not do the list of
Cards
...sage: list(Cards) Traceback (most recent call last): ... AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'There are of course other ways to fix it, but I found that it was the simplest. Using
FiniteEnumeratedSet
instead ofSet
in the tutorial seems unnatural to me since you want to keep it as simple as possible...
I tend to agree indeed; this would be annoying.
Maybe we should eventually make the distinction between sets, sets admitting an iterator, and sets with a distinguished enumeration.
For now, let's say that this will do, unless someone has some additional insight to provide.
Still, any thought about moving this feature to Sets.Finite.CartesianProducts??
comment:41 in reply to: ↑ 40 Changed 4 years ago by
Replying to nthiery:
Replying to vdelecroix:
Maybe we should eventually make the distinction between sets, sets admitting an iterator, and sets with a distinguished enumeration.
Ideally, we would do a conditional inheritance based on the presence of __iter__
. I am not sure it is worth it to complicate anymore the various set categories with an IterableSets
.
For now, let's say that this will do, unless someone has some additional insight to provide.
Still, any thought about moving this feature to
Sets.Finite.CartesianProducts
?
Before it was in EnumeratedSets.CartesianProducts
and not EnumeratedSets.Finite.CartesianProducts
. So I tend to prefer the place it is. Of course, we should support better infinite factors.
Vincent
comment:42 Changed 4 years ago by
 Description modified (diff)
comment:43 Changed 4 years ago by
ping: are we good?
comment:44 Changed 4 years ago by
ping ping: are we good good?
comment:45 Changed 4 years ago by
 Status changed from needs_review to positive_review
Oh, sorry, I missed the ping in my mailbox. Yes, given that noone commented about the Sets thing, I believe we are good. Moving to positive review.
comment:46 Changed 4 years ago by
 Status changed from positive_review to needs_work
comment:47 followup: ↓ 48 Changed 4 years ago by
Oh, I had not noticed the startup module plugin failure. If you see a trivial way to avoid loading the following modules on startup, that would be nice. Otherwise we can live without it:
+ sage.combinat.rigged_configurations.itertools + sage.geometry.itertools + sage.geometry.polyhedron.itertools
comment:48 in reply to: ↑ 47 Changed 4 years ago by
Replying to nthiery:
Oh, I had not noticed the startup module plugin failure. If you see a trivial way to avoid loading the following modules on startup, that would be nice. Otherwise we can live without it:
+ sage.combinat.rigged_configurations.itertools + sage.geometry.itertools + sage.geometry.polyhedron.itertools
It is a problem with the patchbot plugin, Not with my code ;). The module is itertools
and not whatever.the.patchbot.thinks.itertools
.
sage: sage.combinat.rigged_configurations.itertools Traceback (most recent call last): ... AttributeError: 'module' object has no attribute 'itertools'
comment:49 Changed 4 years ago by
More precisely, see issue 71.
comment:50 Changed 4 years ago by
 Status changed from needs_work to positive_review
Oh, I see. Back to positive review then.
Thanks for all the hard work!!!
comment:51 Changed 4 years ago by
 Reviewers changed from Nicolas Thiéry to Nicolas M. Thiéry
comment:52 Changed 4 years ago by
Thanks Nicolas for the careful review.
comment:53 Changed 4 years ago by
 Status changed from positive_review to needs_work
Doctest failure, possibly due to one of these:
0e16148 Trac #18338: bell_polynomial(n,k) should always return a polynomial 1d39e65 Trac #18284: Implement left top and right bottom maps for rigged configurations 9481c0b Trac #18223: cartesian products with orders a677b85 Trac #18044: Implement categories for super algebras/modules 2fef51e Trac #17716: AsymptoticRing and AsymptoticExpression dbd82f3 Trac #17693: mutable poset: a data structure for asymptotic expressions 34f358b Trac #17190: Error in conversion from RR['x,y'] to RR['x'] a87d70f Trac #19357: Bug in Multivariate Laurent Polynomial Ring 20616e0 Trac #19321: provide better hash functions
comment:54 Changed 4 years ago by
 Dependencies set to 17411
comment:55 Changed 4 years ago by
 Commit changed from 22f8b77a3cc2223863396f8d422fbbeec51d1656 to fe857fe40e1ef2082f6c32a479f7b4946e58518c
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
d063050  Fix doctest from update to Coxeter groups.

5f32618  trac #17411 a few doc typo corrections and also some pep8 code changes

66a2290  trac #17411 final pep8 cleanup

0350849  trac #17411 insertion in module_list

0b56cd3  trac #17411 one typo found

24b4b4f  trac #17411 lazy import

e9d30dc  Merge branch 'public/combinat/colored_permutation_groups17411' of trac.sagemath.org:sage into public/combinat/colored_permutation_groups17411

4595847  Making changes based upon Kevin's comments.

3a98f7e  Trac 18411: merge 17411

fe857fe  Trac 18411: fix doctest from #17411

comment:56 Changed 4 years ago by
 Dependencies changed from 17411 to #17411
 Milestone changed from sage6.9 to sage6.10
 Status changed from needs_work to positive_review
fixed the issue from #17411... hoping it is the only one.
comment:57 Changed 4 years ago by
 Status changed from positive_review to needs_work
Try again with the next beta
comment:58 Changed 4 years ago by
 Commit changed from fe857fe40e1ef2082f6c32a479f7b4946e58518c to 525d03837adb1ef1265d44314474f59421ed2363
comment:59 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:60 Changed 4 years ago by
 Status changed from needs_review to positive_review
The change sounds fine to me! Assuming all test pass, back to positive review.
comment:62 Changed 4 years ago by
 Commit changed from 525d03837adb1ef1265d44314474f59421ed2363 to 41af76268e8bc96a6fcf23a2d0c70da58fc6df80
Branch pushed to git repo; I updated commit sha1. New commits:
41af762  Trac 18411: pass keywords in __call__

comment:63 Changed 4 years ago by
...waiting for the patchbot green light...
comment:66 Changed 4 years ago by
With what?
comment:67 Changed 4 years ago by
 Commit changed from 41af76268e8bc96a6fcf23a2d0c70da58fc6df80 to 6e27ddedfb0e8322914e6fd036dbe5b3fef6f996
Branch pushed to git repo; I updated commit sha1. New commits:
6e27dde  Trac 18411: merge sage6.10.beta1

comment:68 Changed 4 years ago by
 Status changed from needs_work to needs_review
Hoping I will not have to rebase once more...
comment:69 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:70 Changed 4 years ago by
 Branch changed from public/18411 to 6e27ddedfb0e8322914e6fd036dbe5b3fef6f996
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Trac 18411: remove occurrences of CartesianProduct