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}}

Answer 1

Python 3, \$O((n - 1)!^{m - 1}nm)\$ expected time

This is a reference answer using a very straightforward and slow rejection sampling algorithm, for the sake of having at least one valid answer. It picks \$m\$ random cycles, checks whether they form a valid solution, and repeats from scratch until they do.

Since there exists at least one valid solution, there must exist at least \$(n - 1)!\$ valid solutions (by relabeling it), so the probability that \$m\$ random cycles happen to be a valid solution is at least \$\frac{(n - 1)!}{(n - 1)!^m}\$. So we expect at most \$(n - 1)^{m-1}\$ iterations of the loop, with each iteration taking \$O(nm)\$ time. (This is a pessimistic analysis that could be improved with a better lower bound on the number of solutions.)

import random

def f(n, m):
    while True:
        cycles = []
        for i in range(m):
            order = list(range(1, n))
            random.shuffle(order)
            cycle = [None] * n
            for a, b in zip([0] + order, order + [0]):
                cycle[a] = b
            cycles.append(cycle)

        if all(len({cycle[j] for cycle in cycles}) == m for j in range(n)):
            return cycles

Try it online!

Answer 2

Python3, ~O(n!):

import collections, copy, random
def cycles(n):
   q, q1 = collections.deque([([], [0 for _ in range(n)], 0, {}, {*range(n)}, collections.defaultdict(set))]), collections.deque()
   while q:
     result, a, s, d, ac, cache = q.popleft()
     if not ac:
        yield a, cache
        continue
     for i, x in enumerate(a):
       if (s or i) and (i not in d and s not in cache[i]):
          l, _cache = copy.deepcopy(a), copy.deepcopy(cache)
          _d = copy.deepcopy(d)
          l[i] = s
          _d[i] = s
          _cache[i].add(s)
          q.append((result, l, i, _d, ac - {s}, _cache))   

def main(n, m):
   cycle, result, cache, seen = [*cycles(n)], [], {}, []
   while 1:
     if len(result) == m and result not in seen: 
        yield result
        result, cache, seen = [], {}, seen + [result]
        continue
     c, _cache = random.choice(cycle)
     if all(not cache.get(j, set())&_cache[j] for j in _cache):
        result.append(c)
        cache = {j:cache.get(j, set())|_cache[j] for j in _cache}

Try it online!