Python:给定一组N个元素，随机选择k次，m次 [英] Python: Given a set of N elements, choose k at random, m times

问题描述

给定一组N个元素，我想选择k个元素的m个随机的，非重复的子集.

Given a set of N elements, I want to choose m random, non-repeating subsets of k elements.

如果我想生成N个选择的 all 个组合，我可以 已经使用 itertools.combination ，所以一种做事的方法我想问的是:

If I was looking to generate all the N choose k combinations, I could have used itertools.combination, so one way to do what I m asking would be:

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)

当然，问题在于此代码首先生成所有可能的排列 all ，而且代价可能很高.

The problem is of course that this code first generates all the possible permutations, and that this can be quite expensive.

另一个次优的解决方案是每次随机选择单个排列(例如select-at -random-from-combinations ，然后进行排序以获得排列)，如果已经选择，则将其丢弃.

Another suboptimal solution would be to choose each time a single permutation at random (e.g. choose-at-random-from-combinations, then sort to get permutation), and discard it if it has already been selected.

有更好的方法吗?

推荐答案

您的第二个解决方案似乎是唯一可行的方法.除非k接近n并且m为大"，否则它将很好地工作，在这种情况下，将会有更多的重复.

Your second solution seems to be the only practical way to do it. It will work well unless k is close to n and m is "large", in which case there will be more repetitions.

我添加了获得所需样本所需的尝试次数.对于m = 50，n = 10，k = 4，通常少于60次尝试.您可以查看其与人口规模和样本数量之间的关系.

I added a count of the tries needed to get the samples we need. For m=50, with n=10 and k=4, it takes usually less than 60 tries. You can see how it goes with the size of your population and your samples.

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

You can use random.sample to get a list of k values without replacement, then sort it and turn it into a tuple. So, we can use a set for keeping only unique results.

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 !

这篇关于Python:给定一组N个元素，随机选择k次，m次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！