I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from S<sub>n</sub> are both asymptotically log n, and the distribution is asymptotically normal. I want to know what a typical permutation of [n] with k(n) cycles "looks like" (in terms of cycle structure), where k(n)/(log n) → ∞ as n → ∞. The special case I have in mind is permutations of [n] with n<sup>1/2</sup> cycles, since I've come across such permutations in another context, but I'm also curious about the more general problem. In order to do this I would like an algorithm that generates permutations of n with k cycles uniformly at random -- that is, it generates each one with probability 1/S(n,k) where S(n,k) is a Stirling number of the first kind -- so that I can experiment on them. (I'd be willing to settle for a Markov chain that converges to this distribution if it does so reasonably quickly.) Unfortunately the only way I know to do this is to take a permutation of [n] uniformly at random (this is easy) and then throw it out if it doesn't have k cycles. If k is far from log(n) this is very inefficient, since those permutations are rare. A few references I've come across that are related: <a href="http://www.combinatorics.org/Volume_13/JOC/v13i1r107p.pdf">This paper of Granville</a> looks at permutations with o(n<sup>1/2-ε</sup>) cycles or Ω(n<sup>1/2+ε</sup>) cycles and shows that their cycle lengths are "Poisson distributed", but right around n<sup>1/2</sup> is a transitional zone. And <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=212&option_lang=eng">this paper of Kazimirov</a> studies "the asymptotic behavior of various statistics" under the distribution I've claimed, but I haven't read it yet because I can't read Russian and I'm waiting for the English translation. Finally, the algorithm I'm looking for might be in one of the fascicles of volume 4 of Knuth, but our library doesn't have them.