Partitions(n).random_element() is extremely slow

[hivert]

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

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: random integer partition, placherel measure

Author: Florent Hivert

Reviewer: Mike Hansen

Merged: sage-4.3.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/7409

[mwhansen]

comment:1

I would think something like

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

[hivert]

comment:3

Attachment: trac_7409_random_partitions.patch.gz

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.

[hivert]

Author: Florent Hivert

[mwhansen]

comment:4

Looks good.

[mwhansen]

Merged: sage-4.3.alpha1

[mwhansen]

Reviewer: Mike Hansen