生成一个随机的列表排列
我怎样随机洗牌，以保持原有的位置？
换句话说，给定一个具有不同元素的列表A ，我想生成它的排列B
- 这个排列是随机的
- 并且对于每个
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
我不知道这样一个排列的恰当的术语（这是“总”？），因此很难search。 正确的名词似乎是“混乱”。
这种排列被称为紊乱。 在实践中，你可以尝试随机排列，直到遇到一个紊乱，他们的比例接近“n”的倒数，如“n”增长。
经过一番研究，我能够实现本文所述的“早期拒绝”algorithm。 它是这样的：
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)
这个想法是：我们继续洗牌数组，一旦我们发现我们正在处理的排列是无效的（ v[i]==i ），我们打破并从头开始。
一个快速testing表明，这个algorithm统一产生所有的紊乱：
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
为了简单起见，我select了这个algorithm， 这个简介概述了其他的想法。
感谢大家 ））
作为一个可能的出发点，Fisher-Yates洗牌就是这样的。
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))
这是Vatine描述的版本：
def derange(xs): for a in xrange(1, len(xs)): b = random.choice(xrange(0, a)) swap(xs, a, b) return xs
一个快速的统计testing：
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
这在其范围内看起来是统一的，并且具有每个元素在每个允许的时隙中出现的相同机会的好的性质。
但不幸的是，这并不包括所有的紊乱。 有9个大小为4的排列（这个公式和一个n = 4的例子在维基百科文章中给出）。
这应该工作
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)
如果调用了太多的迭代，请注意退出代码的variables。 这解释了如[1，1，1]或[3]
编辑
原来，如果你使用大数组（大于15左右），这将是CPU密集型。 使用一个随机生成的100元素arrays，并将其放大到len(array)**3 ，这需要我的三星Galaxy S4很长一段时间来解决。
编辑2
大约1200秒后（20分钟），程序结束，说'总的随机洗牌不可能'。 对于大型数组，你需要非常大量的置换…说len（array）** 10什么的。
码：
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)
这是一个较小的，pythonic语法 –
import random def derange(s): d=s[:] while any([a==b for a,b in zip(d,s)]):random.shuffle(d) return d
它所做的就是将列表拖动到列表中，直到没有元素匹配。 另外，要小心的是，如果一个不能混乱的列表被传递，它将永远运行。当发生重复时，会发生这种情况。 要删除重复，只需调用这个函数derange(list(set(my_list_to_be_deranged))) 。
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
