Opened 8 years ago

Closed 8 years ago

#17248 closed enhancement (fixed)

Rewriting the method cardinality in the SetPartitions_setparts

Reported by: Grégory Châtel Owned by: gchatel
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: cardinality, set partitions
Cc: Viviane Pons, Travis Scrimshaw, Darij Grinberg, Sage Combinat CC user, Nicolas M. Thiéry, Frédéric Chapoton Merged in:
Authors: Grégory Châtel Reviewers: Frédéric Chapoton, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 8bf6e00 (Commits, GitHub, GitLab) Commit: 8bf6e004220fe0eda092938e23f0018a54590d30
Dependencies: Stopgaps:

Status badges

Description

I have changed the cardinality method of the SetPartitions_setparts class. It used to list the set partitions and now it computes the cardinality using basic enumeration formulas.

Change History (11)

comment:1 Changed 8 years ago by Grégory Châtel

Branch: public/combinat/set-partition-cardinality-17248
Commit: 36c150e491b16b1c9662b8f43d43b36f94eeabfd
Status: newneeds_review

comment:2 Changed 8 years ago by git

Commit: 36c150e491b16b1c9662b8f43d43b36f94eeabfda18a343ec6d0192f75d399047df373e5862e3208

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

a18a343Rewriting the cardinality method using enumeration formula.

comment:3 Changed 8 years ago by Frédéric Chapoton

Instead of 2 variables set_size and sum_subset_size, you could use just one : remaining_subset_size, which is the difference.

comment:4 Changed 8 years ago by Vincent Delecroix

Status: needs_reviewneeds_work

Hello,

That's cool you worked on this!

  1. To avoid the if/else inside your loop you can use the method to_exp_dict of partitions:
    sage: S = SetPartitions(13, Partition([4,3,3,2,1]))
    sage: p = S.parts; p
    [4, 3, 3, 2, 1]
    sage: d = p.to_exp_dict(); d
    {1: 1, 2: 1, 3: 2, 4: 1}
    
  1. Minor remark: if you write
    a = 1
    
    in the source code this is a Python integer. It is not bad to use it but it is confusing if you start to mix them with Sage integer which do not behave the same (especially with respect to division).
  1. If you use only Sage integer, there is no need to import factorial and binomial as they are methods of Sage integers
    sage: 10.factorial()
    3628800
    sage: 10.binomial(2)
    45
    
    Using directly those will significantly improve the timings (the import takes time and the function in sage.rings.arith are much more complicated and ends in calling these methods).
  1. It would be nice to have a test like the following:
    sage: SetPartitions(13).cardinality()
    27644437
    sage: sage: sum(SetPartitions(13,p).cardinality() for p in Partitions(13))
    27644437
    

Vincent

comment:5 Changed 8 years ago by git

Commit: a18a343ec6d0192f75d399047df373e5862e3208627efa1fd7d910fb031f17c74da729557ceec588

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

627efa1Refactoring the code according to the remarks of Frederic and Vincent.

comment:6 Changed 8 years ago by Grégory Châtel

Thanks a lot for your comments, It helps me a lot to learn how Sage works.

Do I need to modify the status of this ticket back to "needs review" ?

Last edited 8 years ago by Grégory Châtel (previous) (diff)

comment:7 in reply to:  6 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

Replying to g.chatel:

Thanks a lot for your comments, It helps me a lot to learn how Sage works.

Do I need to modify the status of this ticket back to "needs review" ?

Yes. I did it. Basically the workflow is

  • author does modif
  • author puts in needs review
  • reviewer complains (and possibly provides commit) and set to needs work/needs info

and you repeat until agreement.

Vincent

comment:8 Changed 8 years ago by git

Commit: 627efa1fd7d910fb031f17c74da729557ceec5888bf6e004220fe0eda092938e23f0018a54590d30

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

426e2b1Merge branch 'public/combinat/set-partition-cardinality-17248' of trac.sagemath.org:sage into chatel2
8bf6e00trac #17248 reviewer commit

comment:9 Changed 8 years ago by Frédéric Chapoton

Reviewers: Frédéric Chapoton, Vincent Delecroix

I made a small review commit. If you agree with my changes, you can set this to positive review.

comment:10 Changed 8 years ago by Grégory Châtel

Status: needs_reviewpositive_review

comment:11 Changed 8 years ago by Volker Braun

Branch: public/combinat/set-partition-cardinality-172488bf6e004220fe0eda092938e23f0018a54590d30
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.