2 added 139 characters in body

Naor and Reingold's paperwhich you mention, mentioned in this answer, only explains how to construct a random permutation with a fixed prescribed structure from a given random permuation P.

This is done by taking the simplest possible permutation with the structure you wish to get, and conjugating it by P.

This reduces the problem to choosing a k-cycles cycle structure with the correct distribution, which does not seem to be easier to me.

1

Naor and Reingold's paper which you mention, only explains how to construct a random permutation with a fixed prescribed structure from a given random permuation P.

This is done by taking the simplest possible permutation with the structure you wish to get, and conjugating it by P.

This reduces the problem to choosing a k-cycles cycle structure with the correct distribution, which does not seem to be easier to me.