14
\$\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\$
10
  • \$\begingroup\$ Please either clarify what the ambiguity is that remains or remove the hold on my question. I believe I have corrected everything you asked, and aside from that I don't believe it violates the rules in any way. \$\endgroup\$ Jan 23, 2017 at 23:07
  • \$\begingroup\$ Can you give an example with n=9, m=7? (If you can then there's a further ambiguity, which is what the distribution of the random cycles should be: I presume it's selecting a random set of valid derangements such that each set is selected with equal probability assuming a perfect random number generator, but that's not entirely clear; however, the task being actually possible is a much bigger problem). \$\endgroup\$ Jan 23, 2017 at 23:17
  • \$\begingroup\$ An answer for n=9, m=7 is {{5, 3, 4, 2, 0, 7, 8, 6, 1}, {2, 0, 8, 6, 5, 3, 1, 4, 7}, {1, 4, 6, 7, 8, 2, 3, 0, 5}, {8, 6, 0, 4, 7, 1, 2, 5, 3}, {3, 7, 5, 1, 2, 0, 4, 8, 6}, {4, 5, 7, 8, 3, 6, 0, 1, 2}, {6, 8, 3, 5, 1, 4, 7, 2, 0}} \$\endgroup\$ Jan 24, 2017 at 1:57
  • \$\begingroup\$ I cleared up ambiguity and stated that all the different ways of doing it with m cycles of length n should have the same probability of occurring \$\endgroup\$ Jan 24, 2017 at 2:05
  • 1
    \$\begingroup\$ "The fastest algorithm (in time complexity) wins." There's two parameters here, m and n, so it's not clear how to compare tradeoffs between these. If you mean for m to be linear in n, that would resolve it. \$\endgroup\$
    – xnor
    Jan 24, 2017 at 5:11

2 Answers 2

2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
8
  • \$\begingroup\$ This doesn’t work. next(main(5, 3)) hangs forever about 1 in 6 times. (Convenient that your TIO link only tests 5 times!) I think that’s due to a bug, but even with the bug fixed, a strategy like this can’t possibly work. For example, with n = 6, m = 4, there is no way to extend [1, 2, 3, 4, 5, 0], [2, 3, 5, 0, 1, 4], [3, 4, 1, 5, 0, 2] with a fourth cycle. \$\endgroup\$ Jun 24 at 19:51
  • \$\begingroup\$ No. There do exist solutions for n = 6, m = 4—an example is listed in the challenge—and the challenge requires you to find them all with equal probability. You just can’t use your row-by-row strategy, since you might start with those dead-end rows. This is marked “difficulty level: hard” for a reason. \$\endgroup\$ Jun 24 at 21:08
  • \$\begingroup\$ @AndersKaseorg I was under the impression that only one block of m cycles had to be produced for the solution to be valid (based on "Example outputs"), hence the use of a generator + next. Anyway, I will look deeper into this later. \$\endgroup\$
    – Ajax1234
    Jun 24 at 22:28
  • \$\begingroup\$ I’m skeptical that this strategy or anything similar can satisfy the challenge’s requirement that “All possible sets of m cycles of length n that fit the criteria should have equal probability of occurring”; do you have any reason to believe that it does? Also, your \$O(mn)\$ claim is not even remotely plausible, given that you have at least three nested loops with lots of restart conditions, and you generate less than half an output per second at n = 6, m = 4. \$\endgroup\$ Jun 24 at 23:33
  • \$\begingroup\$ Now this doesn’t have any randomness at all. The challenge asks for a single random block of m cycles, where all valid outputs occur with equal probability. And I don’t know what you’re measuring with \$O(n^3)\$, but it’s definitely wrong. \$\endgroup\$ Jun 25 at 3:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.