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