Python:给定一组 N 个元素，随机选择 k，m 次

Question

给定一组 N 个元素，我想从 k 个元素中随机选择 m 个不重复的子集。

如果我想要生成所有 N choose 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)

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

另一个次优解决方案是每次随机选择一个排列(e.g. choose-at-random-from-combinations，然后排序以获得排列)，如果已经选择则丢弃它。

有更好的方法吗？

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 !