python - 子集的确切数量

Question

我需要使用基本给定集合的 k 元素生成 n 个子集。我知道如何生成所有个子集，但是如何才能生成d个子集？

这是我获取具有 m 元素的所有子集的函数:

def find(S,m):
    return set(itertools.combinations(S, m))

Answer 1

如果你想随机获取它们，可以使用random.sample :

import random
def find(S, m, d):
    return random.sample(list(itertools.combinations(S, m)), d)

如果您打算定期调用该函数，上面的代码将非常低效。对于固定的S和可变的m，可以先建一个字典:

S = "ABCDE"
fixed_dict = {m: list(itertools.combinations(S,m)) for m in range(len(S)+1)}
def find2(m, d):
    return random.sample(fixed_dict[m], d)

一种更高效的方法，可以在需要时针对不同的 S 和 m 填充字典:

comb_dict = {}
def find3(S, m, d):
    try:
        return random.sample(comb_dict[(S,m)], d)
    except KeyError:
        comb_dict[(S, m)] = list(itertools.combinations(S, m))
        return random.sample(comb_dict[(S,m)], d)

对于比较不规则的较大样本，哈希没有多大帮助，您还可以尝试:

def find4(S, m, d):
    combs = set()
    while len(combs) < d:
        combs.add(tuple(sorted(random.sample(S, m))))
    return combs