大佬教程收集整理的这篇文章主要介绍了生成列表的随机排列,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
经过一些研究,我能够实现如本文所述的“早期拒绝”算法。它是这样的:
import random
def 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 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
为了简单起见,我选择此算法,本演示文稿简要概述了其他想法。
以上是大佬教程为你收集整理的生成列表的随机排列全部内容,希望文章能够帮你解决生成列表的随机排列所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。