Timeline for How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 30, 2009 at 12:05 | comment | added | Michael Lugo | Consider the case where I want permutations of [4] with 2 cycles. There are eleven of these: three that are conjugate to (12)(34) and eight that are conjugate to (123)(4). I want to generate each one of these with the same probability, 1/11. The fact that 11 is prime shows that this won't work -- the probabilities that come from this model are going to be sums of products of fractions with 2, 3, or 4 in the denominator. (Actually finding those probabilities is not that hard but won't fit in this box.) | |
| Oct 30, 2009 at 6:25 | history | answered | Mikael Vejdemo-Johansson | CC BY-SA 2.5 |