enhanced sets and cartesian products #18290

videlec · 2015-04-23T14:59:28Z

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])

CC: @nathanncohen @nthiery

Component: categories

Keywords: cartesian_product

Author: Vincent Delecroix

Branch: 707bf1e

Reviewer: Nicolas M. Thiéry

Issue created by migration from https://trac.sagemath.org/ticket/18290

The text was updated successfully, but these errors were encountered:

videlec · 2015-04-23T15:19:32Z

Branch: u/vdelecroix/18290

videlec · 2015-04-23T15:19:32Z

Commit: 7311911

videlec · 2015-04-23T15:19:32Z

New commits:

`7311911`	`Trac 18290: cardinality/is_finite for cartesian products`

videlec · 2015-04-23T15:19:32Z

Changed keywords from none to cartesian_product

nathanncohen · 2015-04-23T15:22:08Z

comment:3

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

nathanncohen · 2015-04-23T15:28:34Z

comment:5

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

videlec · 2015-04-23T15:36:57Z

comment:6

Replying to @nathanncohen:

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.

nathanncohen · 2015-04-23T16:38:30Z

comment:7

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.

sagetrac-git · 2015-04-23T22:41:23Z

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

`0de55d3`	`Trac 18290: upgrade sets and cartesian products`

sagetrac-git · 2015-04-23T22:41:23Z

Changed commit from 7311911 to 0de55d3

sagetrac-git · 2015-04-23T23:06:21Z

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

`b2e9e75`	`Trac 18290: upgrade sets and cartesian products`

sagetrac-git · 2015-04-23T23:06:21Z

Changed commit from 0de55d3 to b2e9e75

sagetrac-git · 2015-04-23T23:57:53Z

Changed commit from b2e9e75 to a55d69f

sagetrac-git · 2015-04-23T23:57:53Z

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

`a55d69f`	`Trac 18290: fix doctest in combinat/tutorial`

videlec · 2015-05-13T06:44:56Z

comment:35

Replying to @nathanncohen:

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

nathanncohen · 2015-05-13T06:49:32Z

comment:36

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

videlec · 2015-05-13T06:55:04Z

comment:37

Replying to @nathanncohen:

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

nathanncohen · 2015-05-13T06:57:44Z

comment:38

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

nathanncohen · 2015-05-13T07:03:51Z

comment:39

Isn't a semigroup a magma too ? O_o

videlec · 2015-05-13T07:07:14Z

comment:40

Replying to @nathanncohen:

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.

videlec · 2015-05-13T07:07:56Z

comment:41

Replying to @nathanncohen:

Isn't a semigroup a magma too ? O_o

It is!

sage: Semigroups().super_categories()
[Category of magmas]

Did you found something strange?

nathanncohen · 2015-05-13T07:11:50Z

comment:42

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

sagetrac-git · 2015-05-13T07:40:23Z

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

`a36b0f2`	`18290: proofreading`

sagetrac-git · 2015-05-13T07:40:23Z

Changed commit from 6389ff2 to a36b0f2

nthiery · 2015-05-13T07:50:52Z

comment:44

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!

sagetrac-git · 2015-05-13T08:46:19Z

Changed commit from a36b0f2 to 3cbe605

sagetrac-git · 2015-05-13T08:46:19Z

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

`3cbe605`	`Trac 18290: specifications in _cartesian_product_of_elements`

videlec · 2015-05-13T08:48:23Z

comment:46

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

sagetrac-git · 2015-05-13T09:52:12Z

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

`b308872`	`Trac 18290: fix doctests`

sagetrac-git · 2015-05-13T09:52:12Z

Changed commit from 3cbe605 to b308872

sagetrac-git · 2015-05-13T09:53:40Z

Changed commit from b308872 to 707bf1e

sagetrac-git · 2015-05-13T09:53:40Z

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

`707bf1e`	`Trac 18290: fix doctests`

videlec · 2015-05-13T11:00:50Z

Reviewer: Nicolas Thiéry

vbraun · 2015-05-13T20:11:33Z

Changed branch from public/18290 to 707bf1e

jdemeyer · 2015-05-27T13:57:43Z

Changed reviewer from Nicolas Thiéry to Nicolas M. Thiéry

jdemeyer · 2015-05-27T13:57:43Z

Changed commit from 707bf1e to none

videlec added this to the sage-6.7 milestone Apr 23, 2015

videlec added c: categories labels Apr 23, 2015

This comment has been minimized.

Sign in to view

videlec changed the title ~~cardinality/is_finite/__hash__ methods for CartesianProduct~~ cardinality and is_finite methods for CartesianProduct Apr 23, 2015

videlec added the s: needs review label Apr 23, 2015

This comment has been minimized.

Sign in to view

videlec added s: needs work and removed s: needs review labels Apr 23, 2015

This comment has been minimized.

Sign in to view

videlec changed the title ~~cardinality and is_finite methods for CartesianProduct~~ enhanced sets and cartesian products Apr 23, 2015

videlec added s: needs review and removed s: needs work labels Apr 23, 2015

videlec added s: positive review and removed s: needs review labels May 13, 2015

vbraun removed the s: positive review label May 13, 2015

vbraun closed this as completed in 04d92fa May 13, 2015

nthiery mentioned this issue Jan 29, 2023

Meta-ticket: Cleanup cartesian products #15425

Open

This was referenced Dec 29, 2022

Maximum recursion depth error when listing points of a projective space #18400

Open

cardinality vs order #18410

Open

get rid of CartesianProduct #18411

Closed

enhanced sets and cartesian products #18290

enhanced sets and cartesian products #18290

Comments

videlec commented Apr 23, 2015

This comment has been minimized.

videlec commented Apr 23, 2015

videlec commented Apr 23, 2015

videlec commented Apr 23, 2015

videlec commented Apr 23, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 23, 2015

This comment has been minimized.

This comment has been minimized.

nathanncohen mannequin commented Apr 23, 2015

videlec commented Apr 23, 2015

nathanncohen mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

This comment has been minimized.

sagetrac-git mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

videlec commented May 13, 2015

nathanncohen mannequin commented May 13, 2015

videlec commented May 13, 2015

nathanncohen mannequin commented May 13, 2015

nathanncohen mannequin commented May 13, 2015

videlec commented May 13, 2015

videlec commented May 13, 2015

nathanncohen mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

nthiery commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

videlec commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

sagetrac-git mannequin commented May 13, 2015

videlec commented May 13, 2015

vbraun commented May 13, 2015

jdemeyer commented May 27, 2015

jdemeyer commented May 27, 2015