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:

Status badges

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)

trac_7409_random_partitions.patch​ (5.6 KB) - added by hivert 13 years ago.

Download all attachments as: .zip

Change History (5)

comment:1 Changed 13 years ago by mhansen

I would think something like 

Partitions(n).random_element(distribution='uniform') #default
Partitions(n).random_element(distribution='plancherel')

comment:2 Changed 13 years ago by hivert

  • Owner changed from mhansen to hivert

Changed 13 years ago by hivert

comment:3 Changed 13 years ago by hivert

  • Authors set to Florent Hivert
  • 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 mhansen

  • 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.