Opened 5 years ago

Closed 5 years ago

#17248 closed enhancement (fixed)

Rewriting the method cardinality in the SetPartitions_setparts

Reported by: g.chatel Owned by: gchatel
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: cardinality, set partitions
Cc: VivianePons, tscrim, darij, sage-combinat, nthiery, chapoton Merged in:
Authors: Grégory Châtel Reviewers: Frédéric Chapoton, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 8bf6e00 (Commits) Commit: 8bf6e004220fe0eda092938e23f0018a54590d30
Dependencies: Stopgaps:

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 5 years ago by g.chatel

  • Branch set to public/combinat/set-partition-cardinality-17248
  • Commit set to 36c150e491b16b1c9662b8f43d43b36f94eeabfd
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit changed from 36c150e491b16b1c9662b8f43d43b36f94eeabfd to a18a343ec6d0192f75d399047df373e5862e3208

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

a18a343Rewriting the cardinality method using enumeration formula.

comment:3 Changed 5 years ago by 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 5 years ago by vdelecroix

  • Status changed from needs_review to needs_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 5 years ago by git

  • Commit changed from a18a343ec6d0192f75d399047df373e5862e3208 to 627efa1fd7d910fb031f17c74da729557ceec588

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

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

comment:6 follow-up: Changed 5 years ago by 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" ?

Last edited 5 years ago by g.chatel (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_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 5 years ago by git

  • Commit changed from 627efa1fd7d910fb031f17c74da729557ceec588 to 8bf6e004220fe0eda092938e23f0018a54590d30

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 5 years ago by chapoton

  • Reviewers set to 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 5 years ago by g.chatel

  • Status changed from needs_review to positive_review

comment:11 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/set-partition-cardinality-17248 to 8bf6e004220fe0eda092938e23f0018a54590d30
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.