Total Derangement (Difficulty Level: Hard)

Question

The problem: Write a function which, given a cycle length n and a number of cycles m, where 'm' is within [2, n-2], generates m random cycles, each of length n, and all of which are derangements of each other. Then n=7, for example, m could be 2, 3, 4, or 5. All possible sets of m cycles of length n that fit the criteria should have equal probability of occurring.

What is a cycle? Imagine you're hopping around a list. Each element in the list is a number corresponding to another position on the list. Start out at the first element, and update your position to be whatever index is at that element:

CycleThrough(list)
{ 
    pos = 0;
    while(true) { pos = list[pos]; }
}

If you can visit every element in the list and get back to the start using this method, it's a cycle. If you can't, it's not. Here are a few examples of cycles:

(0)
(1, 0)
(1, 2, 0)
(2, 0, 1)
(1, 2, 3, 0)
(1, 3, 0, 2)
(2, 4, 1, 0, 3)

Take the last cycle. It goes 0 -> 2 -> 1 -> 4 -> 3 -> 0. What isn't a cycle? Take (4, 0, 3, 2, 1)- this isn't a cycle because it goes 0 -> 4 -> 1 -> 0, and you won't hit 3 or 2. Or take (1, 1) - it goes 0 -> 1 -> 1 -> 1 -> 1... and it never gets back to 0, so it's not a cycle.

What does it mean for two cycles to be deranged? Lets say you have two cycles, cycle A and cycle B. If A[i] never equals B[i], they're derangements of each other. If you have more than two cycles, they're all derangements of each other if all pairs of cycles are derangements.

The fastest algorithm (in time complexity) wins.

Example outputs for n=5, m=3:

{{1, 4, 3, 0, 2}, {3, 0, 4, 2, 1}, {2, 3, 1, 4, 0}}
{{3, 0, 4, 2, 1}, {2, 4, 3, 1, 0}, {4, 3, 1, 0, 2}}
{{3, 0, 1, 4, 2}, {2, 4, 3, 1, 0}, {4, 3, 0, 2, 1}}
{{3, 4, 0, 1, 2}, {1, 2, 4, 0, 3}, {2, 3, 1, 4, 0}}
{{3, 4, 0, 1, 2}, {4, 0, 1, 2, 3}, {1, 2, 3, 4, 0}}
{{4, 2, 0, 1, 3}, {2, 3, 1, 4, 0}, {1, 4, 3, 0, 2}}
{{4, 3, 0, 2, 1}, {2, 4, 1, 0, 3}, {3, 2, 4, 1, 0}}
{{4, 0, 1, 2, 3}, {3, 2, 0, 4, 1}, {2, 4, 3, 1, 0}}
{{3, 0, 1, 4, 2}, {4, 2, 0, 1, 3}, {1, 3, 4, 2, 0}}
{{3, 2, 0, 4, 1}, {4, 0, 1, 2, 3}, {1, 4, 3, 0, 2}}

Example outputs for n = 4...12, m = n-2

{{2, 3, 1, 0}, {3, 2, 0, 1}}
{{4, 0, 1, 2, 3}, {1, 2, 3, 4, 0}, {2, 3, 4, 0, 1}}
{{4, 2, 5, 1, 3, 0}, {2, 5, 4, 0, 1, 3}, {3, 4, 1, 5, 0, 2}, {5, 3, 0, 4, 2, 1}}
{{6, 3, 5, 0, 1, 4, 2}, {1, 5, 4, 2, 6, 3, 0}, {5, 2, 3, 6, 0, 1, 4}, {4, 0, 6, 1, 5, 2, 3}, {3, 6, 1, 4, 2, 0, 5}}
{{7, 0, 3, 6, 1, 2, 4, 5}, {6, 2, 0, 7, 5, 1, 3, 4}, {1, 5, 4, 0, 7, 6, 2, 3}, {5, 3, 6, 4, 0, 7, 1, 2}, {4, 6, 7, 2, 3, 0, 5, 1}, {3, 7, 1, 5, 2, 4, 0, 6}}
{{2, 3, 6, 8, 0, 4, 1, 5, 7}, {8, 5, 0, 2, 1, 6, 7, 3, 4}, {3, 2, 4, 5, 7, 1, 8, 6, 0}, {4, 6, 5, 7, 8, 0, 3, 2, 1}, {1, 8, 7, 4, 6, 3, 2, 0, 5}, {7, 0, 3, 1, 5, 2, 4, 8, 6}, {5, 7, 1, 6, 3, 8, 0, 4, 2}}
{{1, 4, 5, 6, 2, 9, 8, 3, 0, 7}, {4, 2, 7, 1, 9, 3, 5, 0, 6, 8}, {9, 5, 0, 8, 3, 7, 1, 4, 2, 6}, {5, 7, 6, 0, 8, 2, 4, 9, 1, 3}, {7, 6, 8, 9, 5, 0, 3, 1, 4, 2}, {2, 8, 9, 7, 1, 6, 0, 5, 3, 4}, {8, 0, 3, 5, 6, 4, 9, 2, 7, 1}, {6, 3, 4, 2, 0, 1, 7, 8, 9, 5}}
{{3, 4, 1, 5, 8, 9, 0, 10, 6, 7, 2}, {1, 2, 6, 4, 10, 8, 5, 9, 7, 3, 0}, {10, 6, 3, 1, 9, 7, 8, 4, 0, 2, 5}, {8, 3, 0, 7, 2, 6, 10, 5, 9, 1, 4}, {9, 5, 7, 6, 0, 3, 2, 8, 4, 10, 1}, {2, 0, 9, 10, 7, 1, 4, 3, 5, 6, 8}, {6, 7, 5, 8, 3, 4, 1, 2, 10, 0, 9}, {4, 8, 10, 9, 6, 0, 7, 1, 2, 5, 3}, {5, 10, 4, 0, 1, 2, 9, 6, 3, 8, 7}}
{{6, 11, 4, 5, 3, 1, 8, 2, 9, 7, 0, 10}, {1, 4, 8, 9, 10, 11, 5, 3, 7, 6, 2, 0}, {7, 9, 10, 1, 11, 3, 2, 8, 6, 0, 4, 5}, {4, 2, 5, 0, 6, 7, 9, 11, 1, 10, 8, 3}, {10, 8, 7, 6, 5, 0, 4, 1, 3, 11, 9, 2}, {9, 3, 6, 8, 7, 10, 1, 0, 5, 2, 11, 4}, {8, 0, 9, 11, 1, 4, 7, 10, 2, 3, 5, 6}, {3, 6, 0, 10, 2, 9, 11, 5, 4, 8, 1, 7}, {2, 5, 11, 7, 8, 6, 10, 9, 0, 4, 3, 1}, {11, 7, 1, 2, 0, 8, 3, 4, 10, 5, 6, 9}}