Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#18290 closed enhancement (fixed)

enhanced sets and cartesian products

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.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) Commit:
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

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 4 years ago by vdelecroix

  • 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

New commits:

7311911Trac 18290: cardinality/is_finite for cartesian products

comment:2 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:3 follow-up: Changed 4 years ago by ncohen

  • 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? ^^;;

Last edited 4 years ago by ncohen (previous) (diff)

comment:4 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 4 years ago by ncohen

Okayokay, it seems that there is no is_empty method. You ignore my comment above ^^;

comment:6 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by vdelecroix

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 the is_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 4 years ago by ncohen

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.

I'd say that it would be good, but I do not think that I should be patching category codes given my next-to-zero understanding of how it works.

comment:8 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:9 Changed 4 years ago by git

  • Commit changed from 7311911a110c5c3f0c30ab049dbaf66df7e080c7 to 0de55d3765648006a85599140bfba83d175be8f2

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0de55d3Trac 18290: upgrade sets and cartesian products

comment:10 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from cardinality and is_finite methods for CartesianProduct to enhanced sets and cartesian products

comment:11 Changed 4 years ago by git

  • Commit changed from 0de55d3765648006a85599140bfba83d175be8f2 to b2e9e75805c8e1e80acc0f5b4fdf4d142a85fb4f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b2e9e75Trac 18290: upgrade sets and cartesian products

comment:12 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:13 Changed 4 years ago by git

  • Commit changed from b2e9e75805c8e1e80acc0f5b4fdf4d142a85fb4f to a55d69f2b28da2fd4045e303582e3a3d57aebb50

Branch pushed to git repo; I updated commit sha1. New commits:

a55d69fTrac 18290: fix doctest in combinat/tutorial

comment:14 Changed 4 years ago by git

  • Commit changed from a55d69f2b28da2fd4045e303582e3a3d57aebb50 to 2eff7ab551257766a43b3d9fa7b1e637b07188b0

Branch pushed to git repo; I updated commit sha1. New commits:

2eff7abTrac 18290: fix doctest in categories/enumerated_sets.py

comment:15 follow-ups: Changed 4 years ago by jmantysalo

Wasn't there just discussion about avoiding self in docstrings at sage-devel? 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 ; follow-up: Changed 4 years ago by vdelecroix

Replying to jmantysalo:

Wasn't there just discussion about avoiding self in docstrings at sage-devel? 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 example ZZ.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 4 years ago by nthiery

Replying to jmantysalo:

Wasn't there just discussion about avoiding self in docstrings at sage-devel? 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 ; follow-up: Changed 4 years ago by 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.

comment:19 in reply to: ↑ 18 Changed 4 years ago by vdelecroix

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 4 years ago by git

  • Commit changed from 2eff7ab551257766a43b3d9fa7b1e637b07188b0 to 077f5dade93dc826563b4c0702eba6fdd6b8752e

Branch pushed to git repo; I updated commit sha1. New commits:

077f5daTrac 18290: better doc + remove duplications

comment:21 Changed 4 years ago by git

  • Commit changed from 077f5dade93dc826563b4c0702eba6fdd6b8752e to af59b416dde92020daf87f1ad4f83af92a8127ad

Branch pushed to git repo; I updated commit sha1. New commits:

af59b41Trac 18290: fix doctests

comment:22 Changed 4 years ago by git

  • Commit changed from af59b416dde92020daf87f1ad4f83af92a8127ad to d5e9dde8502e52ce78249128502e80ccecef32de

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

98d3e81Trac 18290: upgrade sets and cartesian products
d81c6a4Trac 18290: fix doctest in combinat/tutorial
c924931Trac 18290: fix doctest in categories/enumerated_sets.py
d5e9ddeTrac 18290: fix doctests

comment:23 Changed 4 years ago by vdelecroix

Rebased on sage-6.7.beta3

Vincent

comment:24 Changed 4 years ago by git

  • Commit changed from d5e9dde8502e52ce78249128502e80ccecef32de to 58cf1d14f081a80f33ad1d25ff83ece40dfd6f27

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

10a0e97Trac 18290: upgrade sets and cartesian products
f3ed5afTrac 18290: fix doctest in combinat/tutorial
a0a282eTrac 18290: fix doctest in categories/enumerated_sets.py
6d0274bTrac 18290: fix doctests
58cf1d1Trac 18290: docstring for functions written with im_func

comment:25 Changed 4 years ago by vdelecroix

Rebased on sage-6.7.beta4 + docstring for the overriden functions in cartesian products of finite enumerated sets.

comment:26 Changed 4 years ago by vdelecroix

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 4 years ago by vdelecroix

What should I do for the sake of that ticket?

comment:28 Changed 4 years ago by ncohen

Hire an engineer.

Last edited 4 years ago by ncohen (previous) (diff)

comment:29 Changed 4 years ago by nthiery

  • Branch changed from u/vdelecroix/18290 to u/nthiery/18290

comment:30 Changed 4 years ago by nthiery

  • 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:

c5d600618290: proofreading

comment:31 follow-up: Changed 4 years ago by vdelecroix

  • 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 in categories/* and also in combinat/cartesian_product.
  • I moved is_empty from Magmas.FinitelyGenerated.Unital.ParentMethods.is_empty to Magmas.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:

6389ff2Trac 18290: reviewer comments

comment:32 follow-up: Changed 4 years ago by vdelecroix

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 4 years ago by nthiery

Replying to vdelecroix:

For cardinality vs order 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 ; follow-up: Changed 4 years ago by 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?

Nathann

comment:35 in reply to: ↑ 34 ; follow-up: Changed 4 years ago by vdelecroix

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 ; follow-up: Changed 4 years ago by 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.

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:37 in reply to: ↑ 36 Changed 4 years ago by vdelecroix

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 follow-up: Changed 4 years ago by ncohen

In your earlier comment you explicitly said that you had removed the methods.

comment:39 follow-up: Changed 4 years ago by ncohen

Isn't a semigroup a magma too ? O_o

comment:40 in reply to: ↑ 38 Changed 4 years ago by vdelecroix

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 4 years ago by vdelecroix

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 4 years ago by ncohen

I thought for a second that you had defined is_empty simultaneously for magmas and semigroups, but apparently I was wrong.

comment:43 Changed 4 years ago by git

  • Commit changed from 6389ff27cbcfcc1d51f2b6ad346c79ccd7eebbe3 to a36b0f2960cc019e6267f47cd4f943788f54d220

Branch pushed to git repo; I updated commit sha1. New commits:

a36b0f218290: proofreading

comment:44 Changed 4 years ago by 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?
  • In CartesianProduct._cartesian_product_of_elements, it would be semantically equivalent to use zip rather than iterator.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 a range? I would imagine IntegerRange 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 4 years ago by git

  • Commit changed from a36b0f2960cc019e6267f47cd4f943788f54d220 to 3cbe605b2bfc2d91f878fbde04bebc78d14f4cb7

Branch pushed to git repo; I updated commit sha1. New commits:

3cbe605Trac 18290: specifications in _cartesian_product_of_elements

comment:46 Changed 4 years ago by vdelecroix

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 use zip rather than iterator.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 a range? I would imagine IntegerRange 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 4 years ago by git

  • Commit changed from 3cbe605b2bfc2d91f878fbde04bebc78d14f4cb7 to b308872002aea2434725669f1718dcbc336cfa8b

Branch pushed to git repo; I updated commit sha1. New commits:

b308872Trac 18290: fix doctests

comment:48 Changed 4 years ago by git

  • Commit changed from b308872002aea2434725669f1718dcbc336cfa8b to 707bf1e529e397d10cf2d1e8401229d4f9cd1651

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

707bf1eTrac 18290: fix doctests

comment:49 Changed 4 years ago by vdelecroix

  • Reviewers set to Nicolas Thiéry
  • Status changed from needs_review to positive_review

comment:50 Changed 4 years ago by vbraun

  • Branch changed from public/18290 to 707bf1e529e397d10cf2d1e8401229d4f9cd1651
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:51 Changed 4 years ago by jdemeyer

  • Commit 707bf1e529e397d10cf2d1e8401229d4f9cd1651 deleted
  • Reviewers changed from Nicolas Thiéry to Nicolas M. Thiéry
Note: See TracTickets for help on using tickets.