8
\$\begingroup\$

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}}
\$\endgroup\$
  • 2
    \$\begingroup\$ Fastest in complexity, or fastest in time taken? \$\endgroup\$ – Conor O'Brien Jan 23 '17 at 19:05
  • \$\begingroup\$ Fastest in complexity. Ideally I want an O(n * m) algorithm; not sure if that's possible. O(n * m log(n)) would be the next best bet, followed by O(n * m log(n * m)) \$\endgroup\$ – J. Antonio Perez Jan 23 '17 at 19:16
  • \$\begingroup\$ You're asking for the impossible. Consider n = 4, m = 3. There are six derangements which are single cycles, and no triple which are mutually derangements. \$\endgroup\$ – Peter Taylor Jan 23 '17 at 19:21
  • \$\begingroup\$ I should have been more specific. I mean that m can range between 2 and n-2 inclusive.. \$\endgroup\$ – J. Antonio Perez Jan 23 '17 at 21:15
  • \$\begingroup\$ I fixed the wording of the problem to remove ambiguity. \$\endgroup\$ – J. Antonio Perez Jan 23 '17 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.