Generating random permutation with N cycle Suppose we have integer list from 1 to N. I am interested in generating random permutations such that its cycle notation has only one N cycle.

What algorithms are known to generate random N-cycle permutations?


The canonical method to generate such a random permutation, which is termed cyclic, is Sattolo's algorithm, a variant of the Fisher–Yates shuffle to generate a random general permutation. Its description is terrifically simple:

Swap the last unprocessed element of the list with a random element $a$ that lies strictly before it. Mark $a$ as processed.

