我有一个包含27个元素的数组,但不想生成所有的排列(27!)我需要随机选择5000个排列。任何提示都将有所帮助...
我有一个包含27个元素的数组,但不想生成所有的排列(27!)我需要随机选择5000个排列。任何提示都将有所帮助...
为生成一个排列,请使用random.shuffle
并存储结果的副本。在循环中重复此操作,并每次检查重复项(虽然可能不会有任何重复项)。一旦您的结果集中有5000个项目,请停止。
针对评论中的问题,Python的random模块基于Mersenne Twister,其周期为2**19937-1
,比27!
要大得多,因此应该适合您的用途。
random.shuffle
存在一个严重的缺陷:随着_n_变得更大,大多数随机数生成器的周期比所有排列的总数要小。这意味着在足够大的_n_下,几乎无法生成所有可能的排列,因此这不是真正的随机。 - John Feminella1/10888869450418352160768000000
,但是没有一个相等的概率更大。例如,如果你取 27!+1
个排列,即使其中一个相等的概率很小,没有重复的概率为0。在这种情况下,因为 27! >> 5000
,至少有一个重复的概率为 (1/27)*5000
。虽然仍然很小,但不同于没有重复的情况。 - matteo_cimport random
perm_list = []
for i in range(5000):
temp = range(27)
random.shuffle(temp)
perm_list.append(temp)
print(perm_list)
10888869450418352160768000000
我喜欢大数! :)
AND
10888869450418352160768000001
是质数!!
EDIT:
#with duplicates check as suggested in the comment
perm_list = set()
while len(perm_list)<5000:
temp = range(27)
random.shuffle(temp)
perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?
print perm_list
警告:如果随机数生成器不好,这个程序将永远不会停止!
perms = set()
,perms.add(tuple(temp))
和while len(perms) < 5000
而不是for循环。 - Beni Cherniavsky-Paskintuple(temp)
,但后来我明白了自己是个傻瓜!谢谢你啊,老兄! - Pratik Deoghare# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
for i in range(len(alist)-1):
apermindex, j = divmod(apermindex, len(alist)-i)
alist[i], alist[i+j] = alist[i+j], alist[i]
return alist
用法:perm_given_index(['a','b','c'],3)
此处使用Lehmer代码表示排列,因为j
的值与之匹配。
itertools.permutations
是一个生成器,它不会创建所有排列的列表。您可以跳过随机排列,直到获得5000个。
itertools
按照一定的顺序创建它们,而且排列的数量是有限的。更好的方法是这样做:(1)确定有多少个排列(称这个数字为 N
),(2)然后在范围 0..N-1
中生成 5,000 个不同的随机索引,(3)从 itertools.permutations 生成器中选择与这些索引对应的排列。 - John Feminella您可以尝试实现 random_permutation
itertools recipes。为了方便起见,我使用第三方库more_itertools
来为我们实现此配方:
import more_itertools as mit
iterable = range(27)
mit.random_permutation(iterable)
# (24, 3, 18, 21, 17, 22, 14, 15, 20, 8, 4, 7, 13, 6, 25, 5, 12, 1, 9, 19, 23, 11, 16, 0, 26, 2, 10)
每次调用该函数都会创建一个随机排列。我们可以创建一个生成器,为n
个调用生成这些结果。我们将实现此生成器,并通过简化示例演示随机结果:
def random_permute_generator(iterable, n=10):
"""Yield a random permuation of an iterable n times."""
for _ in range(n):
yield mit.random_permutation(iterable)
list(random_permute_generator(range(10), n=20))
# [(2, 7, 9, 6, 5, 0, 1, 3, 4, 8),
# (7, 3, 8, 1, 2, 6, 4, 5, 9, 0),
# (2, 3, 1, 8, 7, 4, 9, 0, 6, 5),
# (0, 5, 6, 8, 2, 3, 1, 9, 4, 7),
# (0, 8, 1, 9, 4, 5, 7, 2, 3, 6),
# (7, 2, 5, 8, 3, 4, 1, 0, 9, 6),
# (9, 1, 4, 5, 8, 0, 6, 2, 7, 3),
# (3, 6, 0, 2, 9, 7, 1, 4, 5, 8),
# (8, 4, 0, 2, 7, 5, 6, 1, 9, 3),
# (4, 9, 0, 5, 7, 1, 8, 3, 6, 2)
# ...]
n
替换为适当的值,例如:random_permute_generator(iterable, n=5000)
。more_itertools
文档获取关于该工具的更多信息。
def random_permutation(iterable, r=None):
"Random selection from itertools.permutations(iterable, r)"
pool = tuple(iterable)
r = len(pool) if r is None else r
return tuple(random.sample(pool, r))
27!
等于10888869450418352160768000000。 - Mark Byers