Next unicycle Permutation

Question

I want to get the nextPermutation which has just one cycle. I am familiar with the nextPermutation function but this creates also permutations with more than one cycle. I have no idea how to modify this function to create the nextUnicyclePermution

unicycle permutations of length 4:

2341 -> 2413 -> 3142 -> 3421 -> 4123 -> 4312

Answer 1

Here's an initial idea for generating all the unicyclic permutations.

Each unicyclic permutation, in cycle notation, consists of a single cycle of the elements from the original array (e.g. (1 2 3 4) or (4 1 3 2)). Given any unicyclic permutation of an array of n elements, there are n different ways to write that permutation as a simple cycle. For example, the unicyclic permutation (1 2 3 4) can be written as (1 2 3 4), or (2 3 4 1), or (3 4 1 2), or (4 1 2 3). We'll pick a single canonical way of writing out the permutation by enforcing that the first element of the array comes at the front of the cycle notation.

Once we've fixed that element in place, we can enumerate all the unicyclic permutations by simply enumerating all the permutations of the remaining elements in the cycle notation. For example, here's all the unicyclic permutations of four elements:

• (1 2 3 4) ↠ [4, 1, 2, 3]
• (1 2 4 3) ↠ [3, 1, 4, 2]
• (1 3 2 4) ↠ [4, 3, 1, 2]
• (1 3 4 2) ↠ [2, 4, 1, 3]
• (1 4 2 3) ↠ [3, 4, 2, 1]
• (1 4 3 2) ↠ [2, 3, 4, 1]

The general algorithm would then be the following:

• Compute the cycle notation of the current permutation.
• Rotate that cycle notation to put the first element into the first slot.
• Use a standard next-permutation algorithm to advance the last n-1 elements of the cycle notation to their next permutation.
• Reorder the elements to match that cyclic ordering.

There is probably a faster way to enumerate them (with, say, O(1) work done between permutations) and there might be a way to generate them in lexicographical order. But this hopefully gives a starting algorithm to work with!