Opened 4 years ago

Closed 4 months ago

#10534 closed enhancement (fixed)

Cleanup in choose_nk, split_nk, subword, subset

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords: generation, combinatorics, set, subset, partition
Cc: sage-combinat Merged in:
Authors: Vincent Delecroix, Frédéric Chapoton Reviewers: Florent Hivert, Frédéric Chapoton, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 714f266 (Commits) Commit: 714f266d81f57dd6d98daa5598a3b54478c213c8
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

  • deprecate ChooseNK (in sage.combinat.choose_nk) and SplitNK (in sage.combinat.split_nk).
  • clean sage.combinat.subword and sage.combinat.subset
    • inheritance from Parent
    • much better iteration/random generation
    • ...

And become more pep8 compliant ;=)

see also: #16472

Attachments (3)

Change History (66)

comment:1 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from Generation of subsets and partitions enumerated sets to Generation of subwords, subsets and set partitions

comment:2 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:4 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_review to needs_work

comment:5 Changed 3 years ago by vdelecroix

  • Owner vdelecroix deleted

comment:6 Changed 3 years ago by vdelecroix

  • Description modified (diff)
  • Owner set to vdelecroix

comment:7 Changed 3 years ago by vdelecroix

  • Description modified (diff)

comment:8 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:9 follow-up: Changed 3 years ago by hivert

  • Authors changed from vdelecroix to Vincent Delecroix
  • Reviewers set to Florent Hivert

Hi Vincent,

Your patch looks good except a few remarks:

  • the field Author below is for credits. You should put your real name and not your login.
  • the documentation now says:
    [...]
    The elements of the output are tuples of Python int (and not Sage Integer).
    [...]
    It's element are returned as plain list of python int.
    

At least one of those two sentences is wrong. Also they seems a little
redundent. This should be fixed.

I'm sorry for not having the time to put a review patch, nor finish the review
now.

comment:10 in reply to: ↑ 9 Changed 3 years ago by vdelecroix

  • the field Author below is for credits. You should put your real name and not your login.

Thank you for modifying this.

  • the documentation now says:
    [...]
    The elements of the output are tuples of Python int (and not Sage Integer).
    [...]
    It's element are returned as plain list of python int.
    

That's right. Output value are now tuples and it is fully specified.

comment:11 follow-up: Changed 3 years ago by hivert

Hi Vincent,

I need more time to review your long patch. I just notice the following:

file: sage/combinat/choose_nk.py
85	            sage: [0,2] in c52   # trac XXXX 

You probably want to replace XXXX by an actual number. I'll continue my review tomorrow (hopefully)

Florent

comment:12 in reply to: ↑ 11 Changed 3 years ago by vdelecroix

Hi Florent

I need more time to review your long patch.

Certainly. Thanks for the review.

I have three important design questions relative to that patch and the Combinatorial classes which it modify

  • should the attributes of a CombinatorialClass? be visible like S.w or do we prefer S._w (some code in graphs uses a direct call to S.w) ?
  • what should be the inheritance/relations between say Subsets (subset of a given set) and Subsets_k (subset of size k of a given set) ?
  • what should be the output of Subwords ? tuple, list, strings, any user defined type ? Actually, if you initialize it with list (resp. tuple, string) it output lists (resp. tuple, string).

I just notice the following:

file: sage/combinat/choose_nk.py
85	            sage: [0,2] in c52   # trac XXXX 

You probably want to replace XXXX by an actual number.

Done

comment:13 Changed 3 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:14 Changed 3 years ago by vdelecroix

  • Description modified (diff)

Nathan, you should be more explicit when asking for more info...

comment:15 Changed 3 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:16 Changed 2 years ago by nthiery

  • Summary changed from Generation of subwords, subsets and set partitions to Optimizations for the generation of subwords, subsets and set partitions

comment:17 Changed 2 years ago by vdelecroix

I update the file to make it works on sage-5.0. I will update the corresponding patch in the combinat queue.

comment:18 Changed 2 years ago by chapoton

This code breaks a test in polytopes.parallelotope, because this last procedure calls Combinations and expect to receive a list and not a tuple. This has to be cured, maybe by inserting a list() at the appropriate place in this procedure. Please test that the correction works before uploading a new patch.

Please also remove all trailing whitespaces, see the bot report.

comment:19 follow-up: Changed 2 years ago by chapoton

Here is a minimal example of what goes wrong in polytopes.parallelotope :

sage: g=[ vector([1,0]), vector([0,1])]
sage: Combinations(g)

This is a mutability/hash problem, when trying to convert a multiset in a set, apparently..

comment:20 in reply to: ↑ 19 Changed 2 years ago by vdelecroix

Replying to chapoton:

Here is a minimal example of what goes wrong in polytopes.parallelotope :

sage: g=[ vector([1,0]), vector([0,1])]
sage: Combinations(g)

This is a mutability/hash problem, when trying to convert a multiset in a set, apparently..

In the above example, the command fails because the *vector* is not hashable.

comment:21 Changed 2 years ago by vdelecroix

I correct the error and add the ticket number on the first line of the patch (as asked by the patchbot).

comment:22 Changed 2 years ago by chapoton

  • Description modified (diff)

Apply only:

  • trac_10534-generation_of_subsets_and_set_partitions.3.patch

comment:23 Changed 2 years ago by chapoton

new patch, to ensure 100% doctest

Last edited 2 years ago by chapoton (previous) (diff)

comment:24 follow-up: Changed 2 years ago by emchennyc

I got 100% doctest coverage for all the edited files but there was one warning. If someone doesn't mind explaining what is the significance of this, that would be helpful.


SCORE /Applications/sage/devel/sage-main/sage/combinat/subset.py: 100% (33 of 33)

Possibly wrong (function name doesn't occur in doctests):

  • _element_constructor_(self, x):
  • _element_constructor_(self, x):

Also, "devel/sage/sage/tests/interrupt.pyx" timed out when I ran the long doctests.

comment:25 in reply to: ↑ 24 Changed 2 years ago by vdelecroix


SCORE /Applications/sage/devel/sage-main/sage/combinat/subset.py: 100% (33 of 33)

Possibly wrong (function name doesn't occur in doctests):

  • _element_constructor_(self, x):
  • _element_constructor_(self, x):

This is because the methods _element_constructor_(self, x) are not directly tested. There should be a comment "# indirect doctest" after the corresponding test. Basically, this function is used to build an element of a parent, but it is called through the method call of the parent (which is implemented in Parent).

Also, "devel/sage/sage/tests/interrupt.pyx" timed out when I ran the long doctests.

This is much more ennoying and I do not know why.

comment:26 Changed 20 months ago by ncohen

Helloooooooooooooooo !!!

While I read your patch, two things :

  • an "It's" should become an "its"
  • why do you change the ouput type from lists to tuples ?

Btw, sorry I did not answer your comment many months ago, I may have missed the warning from trac : I had set the ticket to needs_info because you seemed to be asking rather fundamental questions which would have had an impact on the patch, so that it would have been a pity to review the patch if you intended to change it so much later.

Have you had an answer from Florent since ?

Nathann

comment:27 Changed 17 months ago by vdelecroix

  • Status changed from needs_review to needs_work
  • Work issues set to does not apply

comment:28 Changed 15 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:29 Changed 9 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:30 Changed 6 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:31 Changed 5 months ago by chapoton

  • Branch set to u/chapoton/10534
  • Commit set to 8e30be38b2e924e4bc4b6a46d68a3a32a1ee7ae5

Hello,

I have made a branch from the latest patch, but only partially. I have not touched the files set_partition and set_partition_ordered.

Maybe one could just try to get this smaller changes in ?


New commits:

48cd968trac 10534: Optimizations for the generation of subwords, subsets and set partitions
8e30be3trac #10534 partial conversion of the mercurial patch

comment:32 follow-up: Changed 5 months ago by vdelecroix

Hi,

You deserve a necromancy badge ;-) I gave up on that ticket since Travis was refactoring a lot in sage.combinat.*. It definitely makes sense to have at least a portion of it. I will have a look.

Vincent

comment:33 Changed 5 months ago by vdelecroix

Ok. From the commit you proposed, I think we could

  • deprecate ChooseNK and SplitNK as it is used nowhere and subsumed by subsets and set partitions.
  • do some more cleaning in combination.py, subset.py and subwords.py:
    • remove the inheritance from CombinatorialClass and make them inherit from Parent. We would set the category to EnumeratedSets().Finite()
    • better iteration
    • make Subwords work with words as input
      sage: Subwords(Word([1,2,3,4,5]))
      Traceback (most recent call last):
      ...
      ValueError: datatype should be str, list or tuple
      
    • etc

If you agree with this, I can modify the ticket description and propose a commit.

Vincent

comment:34 in reply to: ↑ 32 Changed 5 months ago by tscrim

Replying to vdelecroix:

You deserve a necromancy badge ;-) I gave up on that ticket since Travis was refactoring a lot in sage.combinat.*. It definitely makes sense to have at least a portion of it. I will have a look.

I don't really have time right now to keep going through that, as much as I'd like to. +1 on getting this in. I don't remember if I had any (partial) removal of CombinatorialClass in combination.py, subset.py, or subwords.py to give as a starting point, but I don't think I did. However if you have any problems with doing this, I might have some answers so feel free to ask.

Best,
Travis

comment:35 Changed 5 months ago by git

  • Commit changed from 8e30be38b2e924e4bc4b6a46d68a3a32a1ee7ae5 to efd638056cb99427de29b298169299fa171184fc

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

efd6380trac #10534 just a partial pep8 cleanup

comment:36 Changed 5 months ago by chapoton

I have made a clean-up commit, changin only small details such as raise syntax and so on. I will now stop working on that.

I agree with the changes that you propose. I hope there will be no merge problem with my stupid clean-up commit..

Last edited 5 months ago by chapoton (previous) (diff)

comment:37 Changed 5 months ago by vdelecroix

  • Description modified (diff)
  • Summary changed from Optimizations for the generation of subwords, subsets and set partitions to Cleanup in choose_nk, split_nk, subword, subset

comment:38 Changed 5 months ago by vdelecroix

  • Branch changed from u/chapoton/10534 to public/10534
  • Commit changed from efd638056cb99427de29b298169299fa171184fc to 1995fca0cc79b20ffc8863e425e50c614e61a02b

I have some more to push on subsets and subwords... but for tomorrow ;-)


New commits:

052c36etrac #10534: deprecate ChooseNK and use Combinations instead
1995fcatrac #10534: remove imports in choose_nk + deprecate SplitNK

comment:39 Changed 5 months ago by chapoton

  • Work issues does not apply deleted

There are some doctest continuation ... that should be replaced by ....:

comment:40 Changed 5 months ago by git

  • Commit changed from 1995fca0cc79b20ffc8863e425e50c614e61a02b to e858998035ee733bbb4796c47a2b9e843c67c614

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

e858998trac #10534 doctest continuation using ...:

comment:41 Changed 5 months ago by git

  • Commit changed from e858998035ee733bbb4796c47a2b9e843c67c614 to 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46

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

a291564trac #10534: doctest in choose_nk + redraw subset/subword
1cc4187trac #10534: better implementation for subset
65f33c9trac #10534: fix doctests
1d73c1btrac #10534: merge changes of Frederic

comment:42 Changed 5 months ago by vdelecroix

  • Status changed from needs_work to needs_review

Very cool... now we can do

sage: S = Subsets(Subsets(Subsets(3)))
sage: S.cardinality()
115792089237316195423570985008687907853269984665640564039457584007913129639936
sage: S.unrank(14321093401985)
{{{1, 3}, {3}}, {{2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}, {{1, 3}, {2}, {2, 3}, {}, {3}}, {{2}}, {}, {{1, 3}, {1, 2}, {2}, {3}}, {{2}, {1}}, {{1, 2}, {2}, {1}}}
sage: S.random_element()
...

(so I updated the tutorial which had before a #long time for that kind of examples). And moreover no CombinatorialClass anymore.

Needs review!

Vincent

comment:43 Changed 5 months ago by git

  • Commit changed from 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46 to 772615d0b343605327a8089a838c75dad798c1c2

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

772615dtrac #10534 removed unused imports

comment:44 Changed 5 months ago by vdelecroix

  • Description modified (diff)

comment:45 Changed 5 months ago by git

  • Commit changed from 772615d0b343605327a8089a838c75dad798c1c2 to c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984

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

c3979afSome review tweaks and python 3 stuff.

comment:46 follow-up: Changed 5 months ago by tscrim

Hey Vincent, I've gone through and it looks good (I tried to change the element_class workaround, but Set_object_enumerated is actually a subclass of Parent causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3 format. If you're happy with my changes, then positive review. Other things (like removing CombinatorialClass from Combinations and the element_class thing) can be on followups.

comment:47 in reply to: ↑ 46 Changed 5 months ago by vdelecroix

  • Authors changed from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton
  • Reviewers changed from Florent Hivert to Florent Hivert, Frédéric Chapoton, Travis Scrimshaw
  • Status changed from needs_review to positive_review

Replying to tscrim:

Hey Vincent, I've gone through and it looks good (I tried to change the element_class workaround, but Set_object_enumerated is actually a subclass of Parent causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3 format. If you're happy with my changes, then positive review. Other things (like removing CombinatorialClass from Combinations and the element_class thing) can be on followups.

Thanks for your contribution on this!

Vincent

comment:48 Changed 5 months ago by vbraun

Merge failure due to #16067

comment:49 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

comment:50 Changed 5 months ago by git

  • Commit changed from c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984 to 9146bde20c077c880c8f364e99bb8ef4c879de41

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

e574c68trac #16067: changes generated by "2to3 -w -f filter src/sage"
65c8620trac #16067: fix an error generated by "2to3"
1d50592trac #16067: tidying up the generated patch
c68a033Merge branch 'develop' into u/wluebbe/ticket/16067
0cebea1Merge branch 'develop' into u/wluebbe/ticket/16067
0c2486etrac #16067: answered reviewer comments and further improvements
49e52c3trac #16067: fixed duplicate lines found by reviewer
9146bdetrac #10534: merge #16067

comment:51 Changed 5 months ago by vdelecroix

  • Status changed from needs_work to positive_review

All right. The rebase was rather trivial.

comment:52 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long src/sage/misc/sageinspect.py  # 1 doctest failed

comment:53 Changed 5 months ago by git

  • Commit changed from 9146bde20c077c880c8f364e99bb8ef4c879de41 to d9637bdbfa0f65d670c8fbcdb8425661f36c6343

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

d9637bdTrivial doctest fix due to line number changes.

comment:54 Changed 5 months ago by tscrim

  • Status changed from needs_work to positive_review

comment:55 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

Try running the testsuite...

comment:56 Changed 5 months ago by tscrim

I did (again):

travis@travis-sage:~/sage/src/sage/misc$ sage -tp sageinspect.py 
Running doctests with ID 2014-06-15-09-38-19-7033a8ad.
Doctesting 1 file using 4 threads.
sage -t sageinspect.py
    [251 tests, 24.24 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 24.6 seconds
    cpu time: 4.7 seconds
    cumulative wall time: 24.2 seconds
travis@travis-sage:~/sage/src/sage/misc$ sage -tp --long sageinspect.py 
Running doctests with ID 2014-06-15-09-40-50-0dd08e9e.
Doctesting 1 file using 4 threads.
sage -t --long sageinspect.py
    [251 tests, 24.16 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 24.5 seconds
    cpu time: 4.7 seconds
    cumulative wall time: 24.2 seconds

Is there a failure elsewhere (I also checked the failures that the patchbot reported and those passed)?

comment:57 Changed 5 months ago by vdelecroix

Same problem as in #16472

sage -t --long structure/sage_object.pyx
**********************************************************************
File "structure/sage_object.pyx", line 1346, in sage.structure.sage_object.unpickle_all
Failed example:
    sage.structure.sage_object.unpickle_all()  # (4s on sage.math, 2011)
Expected
...
Got:
...
    Failed:
    _class__sage_combinat_choose_nk_ChooseNK__.sobj
    _class__sage_combinat_split_nk_SplitNK_nk__.sobj

If the approach with __setstate__ is more standard then we should go for it here as well.

comment:58 follow-up: Changed 5 months ago by tscrim

Will you be taking care of it Vincent or do you want me to?

comment:59 in reply to: ↑ 58 Changed 5 months ago by vdelecroix

Replying to tscrim:

Will you be taking care of it Vincent or do you want me to?

No, no. I will do it along your lines. Thanks for proposing.

comment:60 Changed 5 months ago by git

  • Commit changed from d9637bdbfa0f65d670c8fbcdb8425661f36c6343 to 714f266d81f57dd6d98daa5598a3b54478c213c8

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

714f266trac #10534: fix pickling

comment:61 Changed 5 months ago by vdelecroix

  • Status changed from needs_work to needs_review

Hey Travis,

Please double check that everything is fine.

Vincent

comment:62 Changed 5 months ago by tscrim

  • Status changed from needs_review to positive_review

LGTM. Thanks Vincent.

comment:63 Changed 4 months ago by vbraun

  • Branch changed from public/10534 to 714f266d81f57dd6d98daa5598a3b54478c213c8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.