经过一些研究，我能够实现如本文所述的“早期拒绝”算法。它是这样的：
import randomdef random_derangement(n): while True: v = [i for i in range(n)] for j in range(n - 1, -1, -1): p = random.randint(0, j) if v[p] == j: break else: v[j], v[p] = v[p], v[j] else: if v[0] != 0: return tuple(v)
这个想法是：我们不断改组数组，一旦发现我们正在处理的排列无效（
v[i]==i），我们就会中断并从头开始。
快速测试表明，该算法会统一生成所有排列：
N = 4# enumerate all derangements for testingimport itertoolscounter = {}for p in itertools.permutations(range(N)): if all(p[i] != i for i in p): counter[p] = 0# make M probes for each derangementM = 5000for _ in range(M*len(counter)): # generate a random derangement p = random_derangement(N) # is it really? assert p in counter # ok, record it counter[p] += 1# the distribution looks uniformfor p, c in sorted(counter.items()): print p, c结果：
(1, 0, 3, 2) 4934(1, 2, 3, 0) 4952(1, 3, 0, 2) 4980(2, 0, 3, 1) 5054(2, 3, 0, 1) 5032(2, 3, 1, 0) 5053(3, 0, 1, 2) 4951(3, 2, 0, 1) 5048(3, 2, 1, 0) 4996
为了简单起见，我选择此算法，本演示文稿简要概述了其他想法。
