# 生成一个随机的列表排列

• 这个排列是随机的
• 并且对于每个`n``a[n] != b[n]`

` `a = [1,2,3,4] b = [4,1,2,3] # good b = [4,2,1,3] # good a = [1,2,3,4] x = [2,4,3,1] # bad` `

` `import random def random_derangement(n): while True: v = 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)` `

` `N = 4 # enumerate all derangements for testing import itertools counter = {} for p in itertools.permutations(range(N)): if all(p[i] != i for i in p): counter[p] = 0 # make M probes for each derangement M = 5000 for _ 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 uniform for 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` `

` `def swap(xs, a, b): xs[a], xs[b] = xs[b], xs[a] def permute(xs): for a in xrange(len(xs)): b = random.choice(xrange(a, len(xs))) swap(xs, a, b)` `

` `def derange(xs): for a in xrange(len(xs) - 1): b = random.choice(xrange(a + 1, len(xs) - 1)) swap(xs, a, b) swap(len(xs) - 1, random.choice(xrange(n - 1))` `

` `def derange(xs): for a in xrange(1, len(xs)): b = random.choice(xrange(0, a)) swap(xs, a, b) return xs` `

` `from collections import Counter def test(n): derangements = (tuple(derange(range(n))) for _ in xrange(10000)) for k,v in Counter(derangements).iteritems(): print('{} {}').format(k, v)` `

`test(4)`

` `(1, 3, 0, 2) 1665 (2, 0, 3, 1) 1702 (3, 2, 0, 1) 1636 (1, 2, 3, 0) 1632 (3, 0, 1, 2) 1694 (2, 3, 1, 0) 1671` `

` `import random totalrandom = False array = [1, 2, 3, 4] it = 0 while totalrandom == False: it += 1 shuffledArray = sorted(array, key=lambda k: random.random()) total = 0 for i in array: if array[i-1] != shuffledArray[i-1]: total += 1 if total == 4: totalrandom = True if it > 10*len(array): print("'Total random' shuffle impossible") exit() print(shuffledArray)` `

` `import random, time totalrandom = False array = [] it = 0 for i in range(1, 100): array.append(random.randint(1, 6)) start = time.time() while totalrandom == False: it += 1 shuffledArray = sorted(array, key=lambda k: random.random()) total = 0 for i in array: if array[i-1] != shuffledArray[i-1]: total += 1 if total == 4: totalrandom = True if it > len(array)**3: end = time.time() print(end-start) print("'Total random' shuffle impossible") exit() end = time.time() print(end-start) print(shuffledArray)` `

` `import random def derange(s): d=s[:] while any([a==b for a,b in zip(d,s)]):random.shuffle(d) return d` `

` `import random a=[1,2,3,4] c=[] i=0 while i < len(a): while 1: k=random.choice(a) #print k,a[i] if k==a[i]: pass else: if k not in c: if i==len(a)-2: if a[len(a)-1] not in c: if k==a[len(a)-1]: c.append(k) break else: c.append(k) break else: c.append(k) break i=i+1 print c` `