我有一个包含27个元素的数组，但不想生成所有的排列（27！）我需要随机选择5000个排列。任何提示都将有所帮助...
6个回答
41
为生成一个排列，请使用random.shuffle并存储结果的副本。在循环中重复此操作，并每次检查重复项（虽然可能不会有任何重复项）。一旦您的结果集中有5000个项目，请停止。
针对评论中的问题，Python的random模块基于Mersenne Twister，其周期为2**19937-1，比27!要大得多，因此应该适合您的用途。
- Mark Byers
6
4+1，但请注意
random.shuffle存在一个严重的缺陷：随着_n_变得更大，大多数随机数生成器的周期比所有排列的总数要小。这意味着在足够大的_n_下，几乎无法生成所有可能的排列，因此这不是真正的随机。 - John Feminella3确实如此，John。Python的随机数生成器拥有2 ** 19937-1的周期，因此它可能已经足够好了。另一个细节是，要获得真正随机的数字，你需要一个真正随机的来源（例如来自放射性衰变），而Python的随机模块仅提供伪随机数。但在常见用法中，当人们说“随机”时，他们实际上指的是“伪随机”，我认为这也是此处帖子的意思。 - Mark Byers
2+1 酷！这是一个有 10888869450418352160768000000 个面的大骰子，任何一个面朝上的概率都是 1/10888869450418352160768000000。重复？绝无可能！！ - Pratik Deoghare
1@PratikDeoghare 这是一个有着6002位数字的大骰子，但它会按照特定已知的模式旋转，并且很多面都有相同的数字。有重复的情况。 - wizzwizz4
它们中任意两个相等的概率是
1/10888869450418352160768000000，但是没有一个相等的概率更大。例如，如果你取 27!+1 个排列，即使其中一个相等的概率很小，没有重复的概率为0。在这种情况下，因为 27! >> 5000，至少有一个重复的概率为 (1/27)*5000。虽然仍然很小，但不同于没有重复的情况。 - matteo_c有没有办法在内置的 random.shuffle 中设置种子？ - Pushkar Nimkar
12
import 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
警告：如果随机数生成器不好，这个程序将永远不会停止！
- Pratik Deoghare
2
为了像Mark建议的那样检查重复项，请使用
perms = set()，perms.add(tuple(temp))和while len(perms) < 5000而不是for循环。 - Beni Cherniavsky-Paskin@Beni，一开始我没有听从你的建议
tuple(temp)，但后来我明白了自己是个傻瓜！谢谢你啊，老兄！ - Pratik Deoghare6
# 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的值与之匹配。
- Dan D.
2
这可能非常好，例如如果您需要存储许多排列以使用整数表示进行压缩。受到启发写了 https://gist.github.com/lukmdo/7049748 - lukmdo
Lehmer编码（和解码）应该被嵌入到核心Python中的某个地方，至少作为itertools的一部分。任何涉及使用排列的场景都需要一种将其转换为相关Lehmer指数的方法。 - Thomas Kimber
6
itertools.permutations是一个生成器，它不会创建所有排列的列表。您可以跳过随机排列，直到获得5000个。
- Cat Plus Plus
3
2这并不是真正的“随机”，因为
itertools 按照一定的顺序创建它们，而且排列的数量是有限的。更好的方法是这样做：（1）确定有多少个排列（称这个数字为 N），（2）然后在范围 0..N-1 中生成 5,000 个不同的随机索引，（3）从 itertools.permutations 生成器中选择与这些索引对应的排列。 - John Feminella1是的，我知道这不是最好的。第一次阅读问题时，我不知何故没有注意到“随机选择”的部分。我不会删除它，也许有人搜索“如何在Python中生成数组的排列？”会发现它有用。 - Cat Plus Plus
@Cat Plus Plus 那就是我 :D - Shon Freelen
3
您可以尝试实现 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文档获取关于该工具的更多信息。
详细信息 对于有兴趣者，这里是实际的配方。
来自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))
- pylang
1
你可能需要使用itertools.permutations()函数。必须得爱那个itertools模块！
注意：2.6版本中新增。
注意：2.6版本中新增。
- ironfroggy
1
2这会太慢了 - 他说他有27个元素。 - Mark Byers
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
27!等于10888869450418352160768000000。 - Mark Byers