Python3, O(n^2):

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!

Randomized version of this solution. All possible cycles of length n are generated in O(n^2) time, and then m cycles are drawn from the cycle pool, with a check to ensure uniqueness. The process of drawing the m cycles and checking for derangement is done in O(n^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!

Python3, O(n^3):

import collections, copy 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): q = collections.deque([([], {}, [*cycles(n)])]) while q: result, cache, cycle = q.popleft()  if len(result) == m:yield result; continue   for i, (a, _cache) in enumerate(cycle):   if all(not cache.get(j, set())&_cache[j] for j in _cache): q.appendleft((result + [a], {j:cache.get(j, set())|_cache[j] for j in _cache}, cycle[:i]+cycle[i+1:])) 

Try it online!

Generates all possible deranged cycles for a given m and n.

Python3, O(n^2):

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!

Randomized version of this solution. All possible cycles of length n are generated in O(n^2) time, and then m cycles are drawn from the cycle pool, with a check to ensure uniqueness. The process of drawing the m cycles and checking for derangement is done in O(n^2).

Python3, O(n*m):

import random, collections, copy def generate(n, _cache, c_cache): a = [0 for _ in range(n)] s, v, p = 0, {*range(n)}, set() cache = copy.deepcopy(_cache) while 1: if not v or p&v:    if len(set(a)) == len(a): return a, cache if c_cache&v == v: return 0, _cache  a = [0 for _ in range(n)] s, v = 0, {*range(n)} p = set() cache = copy.deepcopy(_cache) continue  if s not in cache[(i:=random.choice([*(v - [{0},set()][bool(s)])]))]:  a[i] = s cache[i].add(s) s, v = i, v - {i} else:  p.add(i); c_cache.add(i) def main(n, m): while 1:   cache = collections.defaultdict(set) c_cache = set() result = [] c = 0   while c < m:   a, cache = generate(n, cache, c_cache)   if not a:  c = 0   result = []   cache = collections.defaultdict(set)    c_cache = set()  else: result.append(a); c += 1  yield result 

Try it online!

Python3, O(n^3):

import collections, copy 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): q = collections.deque([([], {}, [*cycles(n)])]) while q: result, cache, cycle = q.popleft() if len(result) == m:yield result; continue for i, (a, _cache) in enumerate(cycle): if all(not cache.get(j, set())&_cache[j] for j in _cache):  q.appendleft((result + [a], {j:cache.get(j, set())|_cache[j] for j in _cache}, cycle[:i]+cycle[i+1:])) 

Try it online!

Generates all possible deranged cycles for a given m and n.