#18290 closed enhancement (fixed)
enhanced sets and cartesian products
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  categories  Keywords:  cartesian_product 
Cc:  ncohen, nthiery  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nicolas M. Thiéry 
Report Upstream:  N/A  Work issues:  
Branch:  707bf1e (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
We implement several missing features of sets, enumerated sets and their cartesian products.
We add methods is_empty
and is_finite
to all sets.
We implement most of the methods for cartesian products of sets and enumerated sets (cardinality, rank/unrank, iteration).
For example, all commands below were hanging
sage: C = cartesian_product([Permutations(7), Permutations(9)]) sage: C.cardinality() 1828915200 sage: C.unrank(143872745) ([1, 5, 3, 6, 2, 4, 7], [5, 3, 2, 4, 7, 8, 9, 6, 1]) sage: C.rank(_) 143872745 sage: C.random_element() # random ([4, 2, 6, 7, 1, 3, 5], [4, 7, 2, 8, 6, 3, 9, 5, 1])
Change History (51)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/18290
 Commit set to 7311911a110c5c3f0c30ab049dbaf66df7e080c7
 Description modified (diff)
 Keywords cartesian_product added
 Status changed from new to needs_review
 Summary changed from cardinality/is_finite/__hash__ methods for CartesianProduct to cardinality and is_finite methods for CartesianProduct
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 followup: ↓ 6 Changed 6 years ago by
 Description modified (diff)
HMmmmmmmm O_o
I don't know enough about this code to be helpful, but computing the cardinality of those sets seems to be too much. Isn't there a 'is_empty' functio in those classes that you could use instead? And you probably should call is_empty
before the is_finite
. Deciding emptyness is probably easier than deciding if it is finite?... Or perhaps not, in some weird cases? ^^;;
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
Okayokay, it seems that there is no is_empty
method. You ignore my comment above ^^;
comment:6 in reply to: ↑ 3 ; followup: ↓ 7 Changed 6 years ago by
Replying to ncohen:
HMmmmmmmm
O_o
I don't know enough about this code to be helpful, but computing the cardinality of those sets seems to be too much. Isn't there a 'is_empty' functio in those classes that you could use instead? And you probably should call
is_empty
before theis_finite
. Deciding emptyness is probably easier than deciding if it is finite?... Or perhaps not, in some weird cases?^^;;
I would love to have an is_empty
... What do you think to add it in the sets category (and set the default implementation to be return not self.cardinality()
?). The code in this branch would be much cleaner with that.
comment:7 in reply to: ↑ 6 Changed 6 years ago by
I would love to have an
is_empty
... What do you think to add it in the sets category (and set the default implementation to bereturn not self.cardinality()
?). The code in this branch would be much cleaner with that.
I'd say that it would be good, but I do not think that I should be patching category codes given my nexttozero understanding of how it works.
comment:8 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:9 Changed 6 years ago by
 Commit changed from 7311911a110c5c3f0c30ab049dbaf66df7e080c7 to 0de55d3765648006a85599140bfba83d175be8f2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
0de55d3  Trac 18290: upgrade sets and cartesian products

comment:10 Changed 6 years ago by
 Description modified (diff)
 Summary changed from cardinality and is_finite methods for CartesianProduct to enhanced sets and cartesian products
comment:11 Changed 6 years ago by
 Commit changed from 0de55d3765648006a85599140bfba83d175be8f2 to b2e9e75805c8e1e80acc0f5b4fdf4d142a85fb4f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b2e9e75  Trac 18290: upgrade sets and cartesian products

comment:12 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:13 Changed 6 years ago by
 Commit changed from b2e9e75805c8e1e80acc0f5b4fdf4d142a85fb4f to a55d69f2b28da2fd4045e303582e3a3d57aebb50
Branch pushed to git repo; I updated commit sha1. New commits:
a55d69f  Trac 18290: fix doctest in combinat/tutorial

comment:14 Changed 6 years ago by
 Commit changed from a55d69f2b28da2fd4045e303582e3a3d57aebb50 to 2eff7ab551257766a43b3d9fa7b1e637b07188b0
Branch pushed to git repo; I updated commit sha1. New commits:
2eff7ab  Trac 18290: fix doctest in categories/enumerated_sets.py

comment:15 followups: ↓ 16 ↓ 17 Changed 6 years ago by
Wasn't there just discussion about avoiding self
in docstrings at sagedevel? I.e. "Return the cardinality of self." should be "of this set" or "of this cartesian product".
Code seems to work. Just to make sure: should cartesian_product([ZZ, ZZ]).unrank(42)
work like for example ZZ.unrank(42)
works?
comment:16 in reply to: ↑ 15 ; followup: ↓ 18 Changed 6 years ago by
Replying to jmantysalo:
Wasn't there just discussion about avoiding
self
in docstrings at sagedevel? I.e. "Return the cardinality of self." should be "of this set" or "of this cartesian product".
I can do that.
Code seems to work. Just to make sure: should
cartesian_product([ZZ, ZZ]).unrank(42)
work like for exampleZZ.unrank(42)
works?
No. The order of enumeration of a cartesian products is lexicographic. So a cartesian product of infinite enumerated sets should even not be an enumerated set!
comment:17 in reply to: ↑ 15 Changed 6 years ago by
Replying to jmantysalo:
Wasn't there just discussion about avoiding
self
in docstrings at sagedevel? I.e. "Return the cardinality of self." should be "of this set" or "of this cartesian product".
My understanding of the discussion was that self
should not be listed in the INPUT section (I actually need to argue further in the thread for I don't necessarily agree). I don't remember it being a problem elsewhere in the docstring. But I need to reread the thread.
That being said, "of this cartesian product" is a bit redundant but it reads nicely to remind the user of the context. So this can be a good idea here.
Cheers,
Nicolas
comment:18 in reply to: ↑ 16 ; followup: ↓ 19 Changed 6 years ago by
Replying to vdelecroix:
No. The order of enumeration of a cartesian products is lexicographic. So a cartesian product of infinite enumerated sets should even not be an enumerated set!
OK. And after the patch at least for x in cartesian_product([ZZ,ZZ])
gives an error.
comment:19 in reply to: ↑ 18 Changed 6 years ago by
Replying to jmantysalo:
Replying to vdelecroix:
No. The order of enumeration of a cartesian products is lexicographic. So a cartesian product of infinite enumerated sets should even not be an enumerated set!
OK. And after the patch at least
for x in cartesian_product([ZZ,ZZ])
gives an error.
I will add it to the doc with a comment.
Though, for infinite sets, we can choose an other order for the enumeration. If so, we can put back this method and implement rank/unrank.
comment:20 Changed 6 years ago by
 Commit changed from 2eff7ab551257766a43b3d9fa7b1e637b07188b0 to 077f5dade93dc826563b4c0702eba6fdd6b8752e
Branch pushed to git repo; I updated commit sha1. New commits:
077f5da  Trac 18290: better doc + remove duplications

comment:21 Changed 6 years ago by
 Commit changed from 077f5dade93dc826563b4c0702eba6fdd6b8752e to af59b416dde92020daf87f1ad4f83af92a8127ad
Branch pushed to git repo; I updated commit sha1. New commits:
af59b41  Trac 18290: fix doctests

comment:22 Changed 6 years ago by
 Commit changed from af59b416dde92020daf87f1ad4f83af92a8127ad to d5e9dde8502e52ce78249128502e80ccecef32de
comment:23 Changed 6 years ago by
Rebased on sage6.7.beta3
Vincent
comment:24 Changed 6 years ago by
 Commit changed from d5e9dde8502e52ce78249128502e80ccecef32de to 58cf1d14f081a80f33ad1d25ff83ece40dfd6f27
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
10a0e97  Trac 18290: upgrade sets and cartesian products

f3ed5af  Trac 18290: fix doctest in combinat/tutorial

a0a282e  Trac 18290: fix doctest in categories/enumerated_sets.py

6d0274b  Trac 18290: fix doctests

58cf1d1  Trac 18290: docstring for functions written with im_func

comment:25 Changed 6 years ago by
Rebased on sage6.7.beta4 + docstring for the overriden functions in cartesian products of finite enumerated sets.
comment:26 Changed 6 years ago by
If I do
class A: f = B.f.im_func """ Some doctests TESTS:: sage: 1+1 2 """
this is not considered as a doctest. But if instead I do
class A: my_string = ( r""" TESTS:: sage: print "Is this a test?" Of course not """ )
then it is considered as a doctest!!
The algorithm used to detect doctests is clearly wrong!
Vincent
comment:27 Changed 6 years ago by
What should I do for the sake of that ticket?
comment:29 Changed 6 years ago by
 Branch changed from u/vdelecroix/18290 to u/nthiery/18290
comment:30 Changed 6 years ago by
 Commit changed from 58cf1d14f081a80f33ad1d25ff83ece40dfd6f27 to c5d6006e918e9be9078d3ac1f16cbbdbe3aa8933
 EnumeratedSets.CartesianProducts.ParentMethods.__iter__  Description of the iterator  Use is_finite or in Sets.Finite? Or put the thing in CartesianProducts.Finite?  unrank: ValueError or IndexError?  Magmas.FinitelyGenerated.Unital.ParentMethods.is_empty: could be an assignment for consistency?  Groups.CartesianProducts.order: could be an assignment for consistency?  Sets.ParentMethods.random_element: use an abstract method + real doc  random_element & friends: do we want to make a tuple before passing the data to cartesian_product_of_elements?
New commits:
c5d6006  18290: proofreading

comment:31 followup: ↓ 34 Changed 6 years ago by
 Branch changed from u/nthiery/18290 to public/18290
 Commit changed from c5d6006e918e9be9078d3ac1f16cbbdbe3aa8933 to 6389ff27cbcfcc1d51f2b6ad346c79ccd7eebbe3
As we discussed on the phone with Nicolas: I removed the abstract methods: is_empty
, is_finite
and random_element
from Sets
. For the first two, we might not want to call cardinality
as this can easily lead to loop (e.g. #18400). As a rationale: a less specialized method should not try to call a more specialized one. For random_element: adding an optional abstract method would pollute the namespace.
 unrank:
IndexError
is what is uniformly incategories/*
and also incombinat/cartesian_product
.  I moved is_empty from
Magmas.FinitelyGenerated.Unital.ParentMethods.is_empty
toMagmas.Unital.is_empty
and everything looks fine  random_element: tuple removed
I will add a second commit for order
vs cardinality
in Groups
.
Vincent
New commits:
6389ff2  Trac 18290: reviewer comments

comment:32 followup: ↓ 33 Changed 6 years ago by
Hello,
For cardinality
vs order
here is the list of files I had to change:
 algebras/quatalg/quaternion_algebra.py
 algebras/steenrod/steenrod_algebra.py
 groups/abelian_gps/abelian_group.py
 groups/abelian_gps/dual_abelian_group.py
 groups/additive_abelian/additive_abelian_group.py
 groups/group.pyx
 groups/indexed_free_group.py
 groups/matrix_gps/coxeter_group.py
 groups/old.pyx
 groups/pari_group.py
 groups/perm_gps/permgroup.py
 groups/semimonomial_transformations/semimonomial_transformation_group.py
 libs/coxeter3/coxeter.pyx
 modular/abvar/finite_subgroup.py
 modular/abvar/torsion_subgroup.py
 modular/arithgroup/arithgroup_generic.py
 modular/dirichlet.py
 rings/contfrac.py
 rings/finite_rings/finite_field_base.pyx
 rings/finite_rings/finite_field_ext_pari.py
 rings/finite_rings/finite_field_givaro.py
 rings/finite_rings/finite_field_ntl_gf2e.py
 rings/finite_rings/finite_field_prime_modn.py
 rings/finite_rings/homset.py
 rings/finite_rings/integer_mod_ring.py
 rings/integer_ring.pyx
 rings/number_field/galois_group.py
 rings/number_field/morphism.py
 rings/number_field/number_field.py
 rings/polynomial/infinite_polynomial_ring.py
 rings/polynomial/polynomial_quotient_ring.py
 rings/qqbar.py
 rings/rational_field.py
 rings/ring.pyx
In particular it concerns not only groups but:
 (multiplicative) groups
 additive (Abelian) groups
 rings
At least Sage is able to start but I am not sure it fits exactly the purpose of the ticket. If you do not mind I will push that commit in #18410.
Vincent
comment:33 in reply to: ↑ 32 Changed 6 years ago by
Replying to vdelecroix:
For
cardinality
vsorder
here is the list of files I had to change: ...
Thanks!
At least Sage is able to start but I am not sure it fits exactly the purpose of the ticket. If you do not mind I will push that commit in #18410.
+1
comment:34 in reply to: ↑ 31 ; followup: ↓ 35 Changed 6 years ago by
As a rationale: a less specialized method should not try to call a more specialized one.
Are the 'new rationales' just made up when we need them, or should we stop having .cardinality()
call __iter__
, as it is exactly the same pattern?
Nathann
comment:35 in reply to: ↑ 34 ; followup: ↓ 36 Changed 6 years ago by
Replying to ncohen:
As a rationale: a less specialized method should not try to call a more specialized one.
Are the 'new rationales' just made up when we need them, or should we stop having
.cardinality()
call__iter__
, as it is exactly the same pattern?
;) I agree with Nathann that it is perhaps not the best default. Though, let us keep it independent of this ticket. My motivation for the rationale was to avoid loops like
 is_finite asks cardinality
 cardinality asks is_finite before starting to iterate
(which is exactly the problem with projective scheme).
On the other hand, there is sometimes nothing else to do than going through the list of elements to get the cardinality. And you know it: sage.graphs.independent_sets.IndependentSets
.
Vincent
comment:36 in reply to: ↑ 35 ; followup: ↓ 37 Changed 6 years ago by
On the other hand, there is sometimes nothing else to do than going through the list of elements to get the cardinality. And you know it:
sage.graphs.independent_sets.IndependentSets
.
The same goes for is_empty
. Sometimes all you can do is run the enumeration.
Nathann
comment:37 in reply to: ↑ 36 Changed 6 years ago by
Replying to ncohen:
On the other hand, there is sometimes nothing else to do than going through the list of elements to get the cardinality. And you know it:
sage.graphs.independent_sets.IndependentSets
.The same goes for
is_empty
. Sometimes all you can do is run the enumeration.
This is exactly what I did:
class EnumeratedSets: class ParentMethods: def is_empty(self): try: iter(self).next() except StopIteration: return False else: return True
comment:38 followup: ↓ 40 Changed 6 years ago by
In your earlier comment you explicitly said that you had removed the methods.
comment:39 followup: ↓ 41 Changed 6 years ago by
Isn't a semigroup a magma too ? O_o
comment:40 in reply to: ↑ 38 Changed 6 years ago by
Replying to ncohen:
In your earlier comment you explicitly said that you had removed the methods.
I removed it at the level of Sets
where the implementation was return self.cardinality() == 0
. Not at the level of enumerated sets. So most parents will have a is_empty
.
comment:41 in reply to: ↑ 39 Changed 6 years ago by
Replying to ncohen:
Isn't a semigroup a magma too ?
O_o
It is!
sage: Semigroups().super_categories() [Category of magmas]
Did you found something strange?
comment:42 Changed 6 years ago by
I thought for a second that you had defined is_empty
simultaneously for magmas and semigroups, but apparently I was wrong.
comment:43 Changed 6 years ago by
 Commit changed from 6389ff27cbcfcc1d51f2b6ad346c79ccd7eebbe3 to a36b0f2960cc019e6267f47cd4f943788f54d220
Branch pushed to git repo; I updated commit sha1. New commits:
a36b0f2  18290: proofreading

comment:44 Changed 6 years ago by
I have been through Vincent's last commit. I pushed too minor fixes. I have only a couple points I am wondering about:
 Do we want to import ZZ in sage.sets.cartesian_product? Can we do a local import or lazy import? Or is it just ok?
 In
CartesianProduct._cartesian_product_of_elements
, it would be semantically equivalent to usezip
rather thaniterator.izip
since we anyway build a tuple right after. Just curious, is one faster than the other in practice (it's a tradeoff between building a list for nothing and using another layer of iterators)?
 Please update the documentation of
Sets.CartesianProducts.ParentMethods._cartesian_product_of_elements
to specify that it should accept any iterable.
 _sets_keys(): do we really want an
IntegerRange
rather than arange
? I would imagineIntegerRange
could be faster for containment testing and slower for iteration, so again a tradeoff.
In any cases, I'll be busy all day and don't have a strong opinion on either of the above points. So please make the choice you feel right. And then I consider this as good to go.
Thanks Vincent for all the work!
comment:45 Changed 6 years ago by
 Commit changed from a36b0f2960cc019e6267f47cd4f943788f54d220 to 3cbe605b2bfc2d91f878fbde04bebc78d14f4cb7
Branch pushed to git repo; I updated commit sha1. New commits:
3cbe605  Trac 18290: specifications in _cartesian_product_of_elements

comment:46 Changed 6 years ago by
Replying to nthiery:
I have been through Vincent's last commit. I pushed too minor fixes. I have only a couple points I am wondering about:
 Do we want to import ZZ in sage.sets.cartesian_product? Can we do a local import or lazy import? Or is it just ok?
I think this is fine. I would find it strange to import it in sage.categories.*
but sage.sets.cartesian_product
is lazily imported.
 In
CartesianProduct._cartesian_product_of_elements
, it would be semantically equivalent to usezip
rather thaniterator.izip
since we anyway build a tuple right after. Just curious, is one faster than the other in practice (it's a tradeoff between building a list for nothing and using another layer of iterators)?
Here you are not building the list from the pairs (c,x)
but by calling c(x)
. So I guess that izip
is always better. From the timing it is very similar and izip
gets much better as the size of the lists increase. (moreover in Python 3
the izip
is just deleted and zip
becomes izip
).
 Please update the documentation of
Sets.CartesianProducts.ParentMethods._cartesian_product_of_elements
to specify that it should accept any iterable.
done.
 _sets_keys(): do we really want an
IntegerRange
rather than arange
? I would imagineIntegerRange
could be faster for containment testing and slower for iteration, so again a tradeoff.
It is much faster for containment test and it is currently the only way it is used in sage.sets.cartesian_product
(the method cartesian_projection
). If the iteration is slower, then we should just make it faster in IntegerRange
!
In any cases, I'll be busy all day and don't have a strong opinion on either of the above points. So please make the choice you feel right. And then I consider this as good to go.
I am running the long tests and will set positive review if everything is fine.
Vincent
comment:47 Changed 6 years ago by
 Commit changed from 3cbe605b2bfc2d91f878fbde04bebc78d14f4cb7 to b308872002aea2434725669f1718dcbc336cfa8b
Branch pushed to git repo; I updated commit sha1. New commits:
b308872  Trac 18290: fix doctests

comment:48 Changed 6 years ago by
 Commit changed from b308872002aea2434725669f1718dcbc336cfa8b to 707bf1e529e397d10cf2d1e8401229d4f9cd1651
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
707bf1e  Trac 18290: fix doctests

comment:49 Changed 6 years ago by
 Reviewers set to Nicolas Thiéry
 Status changed from needs_review to positive_review
comment:50 Changed 6 years ago by
 Branch changed from public/18290 to 707bf1e529e397d10cf2d1e8401229d4f9cd1651
 Resolution set to fixed
 Status changed from positive_review to closed
comment:51 Changed 6 years ago by
 Commit 707bf1e529e397d10cf2d1e8401229d4f9cd1651 deleted
 Reviewers changed from Nicolas Thiéry to Nicolas M. Thiéry
New commits:
Trac 18290: cardinality/is_finite for cartesian products