Python：在一组N个元素中，随机选择k个元素，进行m次。

Question

给定一个包含N个元素的集合，我想要选择m个大小为k的随机且不重复的子集。

如果我想生成所有的N个元素中选取k个元素的组合，我可以使用itertools.combination，因此实现我所要求的功能的一种方法是：

import numpy as np
import itertools
n=10
A = np.arange(n)
k=4
m=5
result = np.random.permutation([x for x in itertools.permutations(A,k)])[:m]
print(result)

问题当然是这段代码首先会生成所有可能的排列，而这可能非常昂贵。

另一种次优的解决方案是每次随机选择一个排列（例如从组合中随机选择），然后进行排序以获得排列，并且如果已经选择则将其丢弃。

有更好的方法来解决这个问题吗？

- ntg

---

制作一个索引列表，随机选择一个，从列表中删除，重复k次。 - user1781434

@Tobias，这将完全相当于随机选择排列，您仍然需要检查是否选择了相同的排列并将其丢弃。 - Carlo

https://dev59.com/oWUp5IYBdhLWcg3wHUri - DhruvPathak

有没有人在使用 itertools 制作了一个无法想象的长的组合列表，在思考他们正在做什么之前就崩溃了他们的Python核心，并因此来到这里的？ - eric

Answer 1

你的第二个解决方案似乎是唯一可行的方法。除非k接近n且m“大”，否则它将起作用良好，在这种情况下，将会有更多重复。

我添加了获取所需样本所需尝试次数的计数。对于m=50，n=10且k=4，通常需要少于60次尝试。您可以根据您的人口数量和样本量来查看其进展。

您可以使用random.sample获得一个不重复的k值列表，然后对其进行排序并转换为元组。因此，我们可以使用一个set仅保留唯一结果。

import random

n = 10
A = list(range(n))
k = 4
m = 5

samples = set()
tries = 0
while len(samples) < m:
    samples.add(tuple(sorted(random.sample(A, k))))
    tries += 1

print(samples)
print(tries)

# {(1, 4, 5, 9), (0, 3, 6, 8), (0, 4, 7, 8), (3, 5, 7, 9), (1, 2, 3, 4)}
# 6
# 6 tries this time !

- Thierry Lathuille

---

+1 给你的代码和学习。使用 samples=set() 等非常聪明。我想在我的实际生活中采用你的代码。 - ntg

Answer 2

最简单的方法是使用 random.shuffle(range) 然后取前k个元素（需要重复操作直到收集到m个有效样本）。

当然，这种过程不能保证唯一的样本。如果确实需要，请将新样本与历史哈希进行比较。

自Python2.3以来，可以使用 random.sample(range, k) 更有效地生成样本。

- AndreyS Scherbakov

---

没错。但是处理所有组合的成本确实更高。 - AndreyS Scherbakov