9.1

Idea. Build the permutation one position at a time. At index i we may choose any value v that has not been used yet and satisfies v ≠ i. If only one value remains for the last position we must also check that it does not equal that position; if it does, no extension is possible and we back-track. A Boolean array used[1…n] lets us test availability in O(1).

Pseudocode
procedure derange(i): ── current position (1-based)
  if i > n: ── all positions filled
    output perm
    return
  for v = 1 to n:
    if not used[v] and v ≠ i:
      perm[i] = v; used[v] = true
      derange(i+1)
      used[v] = false

Extra pruning. If exactly one unused value r remains before the recursive call, we can test r ≠ (i+1); if it fails, we skip this branch entirely, cutting the search tree roughly in half for large [math]n[/math].

Python 3 implementation

def derangements(n): perm = [0]*n used = [False]* (n+1) out = [] def backtrack(i): # i is 0-based here if i == n: out.append(perm.copy()) return remaining = n - i # quick pruning when one element is left if remaining == 1: r = next(v for v in range(1, n+1) if not used[v]) if r == i+1: # would fall in its own place return for v in range(1, n+1): if not used[v] and v != i+1: perm[i] = v used[v] = True backtrack(i+1) used[v] = False backtrack(0) return out

Complexity. The procedure visits exactly the [math]!n[/math] valid permutations; with [math]O(n)[/math] work to produce each, the total running time is [math]O(n·!n)[/math] and the auxiliary space is [math]O(n)[/math].

Back to Chapter 9