Opened 13 years ago
Closed 13 years ago
#7409 closed enhancement (fixed)
Partitions(n).random_element() is extremely slow
Reported by: | hivert | Owned by: | hivert |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3 |
Component: | combinatorics | Keywords: | random integer partition, placherel measure |
Cc: | sage-combinat | Merged in: | sage-4.3.alpha1 |
Authors: | Florent Hivert | Reviewers: | Mike Hansen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
It is currently implemented by building the list ! Here are some suggestions: Look at
http://www.site.uottawa.ca/~ivan/F49-int-part.pdf
Thanks to #7408 we have a fast algorithm for generating partitions with Plancherel measure. So I suggest the following interface:
Paritions(n).random_element()
default to
Partitions(n).random_element_uniform()
and to implement
Partitions(n).random_element_Plancherel()
Any comment about the interface ?
Cheers,
Florent
Attachments (1)
Change History (5)
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
- Owner changed from mhansen to hivert
Changed 13 years ago by
comment:3 Changed 13 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
I implemented an algorithm from "Nijenhuis, Wilf, Combinatorial Algorithms" which looks reasonably fast. There is certainly room for improvement. However, It will be done later if needed.
comment:4 Changed 13 years ago by
- Merged in set to sage-4.3.alpha1
- Resolution set to fixed
- Reviewers set to Mike Hansen
- Status changed from needs_review to closed
Looks good.
Note: See
TracTickets for help on using
tickets.
I would think something like