Opened 12 years ago
Closed 8 years ago
#10534 closed enhancement (fixed)
Cleanup in choose_nk, split_nk, subword, subset
Reported by:  Vincent Delecroix  Owned by:  Vincent Delecroix 

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  generation, combinatorics, set, subset, partition 
Cc:  Sage Combinat CC user  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, GitHub, GitLab)  Commit:  714f266d81f57dd6d98daa5598a3b54478c213c8 
Dependencies:  Stopgaps: 
Description (last modified by )
 deprecate
ChooseNK
(insage.combinat.choose_nk
) andSplitNK
(insage.combinat.split_nk
).  clean
sage.combinat.subword
andsage.combinat.subset
 inheritance from
Parent
 much better iteration/random generation
 ...
 inheritance from
And become more pep8 compliant ;=)
see also: #16472
Attachments (3)
Change History (66)
comment:1 Changed 12 years ago by
Description:  modified (diff) 

Summary:  Generation of subsets and partitions enumerated sets → Generation of subwords, subsets and set partitions 
comment:2 Changed 12 years ago by
Description:  modified (diff) 

Status:  new → needs_review 
comment:3 Changed 12 years ago by
Description:  modified (diff) 

comment:4 Changed 11 years ago by
Description:  modified (diff) 

Status:  needs_review → needs_work 
comment:5 Changed 11 years ago by
Owner:  Vincent Delecroix deleted 

comment:6 Changed 11 years ago by
Description:  modified (diff) 

Owner:  set to Vincent Delecroix 
comment:7 Changed 11 years ago by
Description:  modified (diff) 

comment:8 Changed 11 years ago by
Status:  needs_work → needs_review 

comment:9 followup: 10 Changed 11 years ago by
Authors:  vdelecroix → Vincent Delecroix 

Reviewers:  → Florent Hivert 
comment:10 Changed 11 years ago by
 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.
Changed 11 years ago by
Attachment:  trac_10534generation_of_subsets_and_set_partitions.patch added 

comment:11 followup: 12 Changed 11 years ago by
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 Changed 11 years ago by
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 XXXXYou probably want to replace XXXX by an actual number.
Done
comment:13 Changed 11 years ago by
Status:  needs_review → needs_info 

comment:14 Changed 10 years ago by
Description:  modified (diff) 

Nathan, you should be more explicit when asking for more info...
comment:15 Changed 10 years ago by
Description:  modified (diff) 

Status:  needs_info → needs_review 
comment:16 Changed 10 years ago by
Summary:  Generation of subwords, subsets and set partitions → Optimizations for the generation of subwords, subsets and set partitions 

comment:17 Changed 10 years ago by
I update the file to make it works on sage5.0. I will update the corresponding patch in the combinat queue.
comment:18 Changed 10 years ago by
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 followup: 20 Changed 10 years ago by
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 Changed 10 years ago by
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.
Changed 10 years ago by
Attachment:  trac_10534generation_of_subsets_and_set_partitions.2.patch added 

comment:21 Changed 10 years ago by
I correct the error and add the ticket number on the first line of the patch (as asked by the patchbot).
comment:22 Changed 10 years ago by
Description:  modified (diff) 

Apply only:
 trac_10534generation_of_subsets_and_set_partitions.3.patch
Changed 10 years ago by
Attachment:  trac_10534generation_of_subsets_and_set_partitions.3.patch added 

comment:24 followup: 25 Changed 10 years ago by
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/sagemain/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 Changed 10 years ago by
SCORE /Applications/sage/devel/sagemain/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 10 years ago by
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 9 years ago by
Status:  needs_review → needs_work 

Work issues:  → does not apply 
comment:28 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:29 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:30 Changed 8 years ago by
Milestone:  sage6.2 → sage6.3 

comment:31 Changed 8 years ago by
Branch:  → u/chapoton/10534 

Commit:  → 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:
48cd968  trac 10534: Optimizations for the generation of subwords, subsets and set partitions

8e30be3  trac #10534 partial conversion of the mercurial patch

comment:32 followup: 34 Changed 8 years ago by
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 8 years ago by
Ok. From the commit you proposed, I think we could
 deprecate
ChooseNK
andSplitNK
as it is used nowhere and subsumed by subsets and set partitions.  do some more cleaning in
combination.py
,subset.py
andsubwords.py
: remove the inheritance from
CombinatorialClass
and make them inherit fromParent
. We would set the category toEnumeratedSets().Finite()
 better iteration
 make
Subwords
work with words as inputsage: Subwords(Word([1,2,3,4,5])) Traceback (most recent call last): ... ValueError: datatype should be str, list or tuple
 etc
 remove the inheritance from
If you agree with this, I can modify the ticket description and propose a commit.
Vincent
comment:34 Changed 8 years ago by
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 8 years ago by
Commit:  8e30be38b2e924e4bc4b6a46d68a3a32a1ee7ae5 → efd638056cb99427de29b298169299fa171184fc 

Branch pushed to git repo; I updated commit sha1. New commits:
efd6380  trac #10534 just a partial pep8 cleanup

comment:36 Changed 8 years ago by
I have made a cleanup 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 cleanup commit..
comment:37 Changed 8 years ago by
Description:  modified (diff) 

Summary:  Optimizations for the generation of subwords, subsets and set partitions → Cleanup in choose_nk, split_nk, subword, subset 
comment:38 Changed 8 years ago by
Branch:  u/chapoton/10534 → public/10534 

Commit:  efd638056cb99427de29b298169299fa171184fc → 1995fca0cc79b20ffc8863e425e50c614e61a02b 
comment:39 Changed 8 years ago by
Work issues:  does not apply 

There are some doctest continuation ...
that should be replaced by ....:
comment:40 Changed 8 years ago by
Commit:  1995fca0cc79b20ffc8863e425e50c614e61a02b → e858998035ee733bbb4796c47a2b9e843c67c614 

Branch pushed to git repo; I updated commit sha1. New commits:
e858998  trac #10534 doctest continuation using ...:

comment:41 Changed 8 years ago by
Commit:  e858998035ee733bbb4796c47a2b9e843c67c614 → 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46 

comment:42 Changed 8 years ago by
Status:  needs_work → 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 8 years ago by
Commit:  1d73c1b243dcc5fd25ccef10af5f3edff31e9d46 → 772615d0b343605327a8089a838c75dad798c1c2 

Branch pushed to git repo; I updated commit sha1. New commits:
772615d  trac #10534 removed unused imports

comment:44 Changed 8 years ago by
Description:  modified (diff) 

comment:45 Changed 8 years ago by
Commit:  772615d0b343605327a8089a838c75dad798c1c2 → c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984 

Branch pushed to git repo; I updated commit sha1. New commits:
c3979af  Some review tweaks and python 3 stuff.

comment:46 followup: 47 Changed 8 years ago by
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 Changed 8 years ago by
Authors:  Vincent Delecroix → Vincent Delecroix, Frédéric Chapoton 

Reviewers:  Florent Hivert → Florent Hivert, Frédéric Chapoton, Travis Scrimshaw 
Status:  needs_review → positive_review 
Replying to tscrim:
Hey Vincent, I've gone through and it looks good (I tried to change the
element_class
workaround, butSet_object_enumerated
is actually a subclass ofParent
causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3format
. If you're happy with my changes, then positive review. Other things (like removingCombinatorialClass
fromCombinations
and theelement_class
thing) can be on followups.
Thanks for your contribution on this!
Vincent
comment:49 Changed 8 years ago by
Status:  positive_review → needs_work 

comment:50 Changed 8 years ago by
Commit:  c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984 → 9146bde20c077c880c8f364e99bb8ef4c879de41 

Branch pushed to git repo; I updated commit sha1. New commits:
e574c68  trac #16067: changes generated by "2to3 w f filter src/sage"

65c8620  trac #16067: fix an error generated by "2to3"

1d50592  trac #16067: tidying up the generated patch

c68a033  Merge branch 'develop' into u/wluebbe/ticket/16067

0cebea1  Merge branch 'develop' into u/wluebbe/ticket/16067

0c2486e  trac #16067: answered reviewer comments and further improvements

49e52c3  trac #16067: fixed duplicate lines found by reviewer

9146bde  trac #10534: merge #16067

comment:51 Changed 8 years ago by
Status:  needs_work → positive_review 

All right. The rebase was rather trivial.
comment:52 Changed 8 years ago by
Status:  positive_review → needs_work 

sage t long src/sage/misc/sageinspect.py # 1 doctest failed
comment:53 Changed 8 years ago by
Commit:  9146bde20c077c880c8f364e99bb8ef4c879de41 → d9637bdbfa0f65d670c8fbcdb8425661f36c6343 

Branch pushed to git repo; I updated commit sha1. New commits:
d9637bd  Trivial doctest fix due to line number changes.

comment:54 Changed 8 years ago by
Status:  needs_work → positive_review 

comment:56 Changed 8 years ago by
I did (again):
travis@travissage:~/sage/src/sage/misc$ sage tp sageinspect.py Running doctests with ID 201406150938197033a8ad. 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@travissage:~/sage/src/sage/misc$ sage tp long sageinspect.py Running doctests with ID 201406150940500dd08e9e. 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 8 years ago by
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 followup: 59 Changed 8 years ago by
Will you be taking care of it Vincent or do you want me to?
comment:59 Changed 8 years ago by
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 8 years ago by
Commit:  d9637bdbfa0f65d670c8fbcdb8425661f36c6343 → 714f266d81f57dd6d98daa5598a3b54478c213c8 

Branch pushed to git repo; I updated commit sha1. New commits:
714f266  trac #10534: fix pickling

comment:61 Changed 8 years ago by
Status:  needs_work → needs_review 

Hey Travis,
Please double check that everything is fine.
Vincent
comment:63 Changed 8 years ago by
Branch:  public/10534 → 714f266d81f57dd6d98daa5598a3b54478c213c8 

Resolution:  → fixed 
Status:  positive_review → closed 
Hi Vincent,
Your patch looks good except a few remarks:
I'm sorry for not having the time to put a review patch, nor finish the review now.