python - 从多重集中均匀采样

Question

给定整数集 {1,...,n}，我想从 binom{n+k-1}{k} 大小为 k 的不同多子集中均匀采样。有没有一种有效的方法来做到这一点？

例如，集合 {1,2,3} 有 6 个大小为 2 的多子集。它们是 {1,2}、{2,3}、{1,3}、{1,1}、 {2,2}, {3,3}。

Answer 1

是的。因为你知道有 (n+k-1) choose k 这样的多子集，你可能知道 stars and bars其解决方案提供该公式的组合问题。该问题的解决方案建议采用抽样程序来生成多子集:随机选择一种方式来放置 k 星和 n-1 条，然后确定条如何将星分成组:

import random
import collections

stars = set(random.sample(xrange(n+k-1), k))
multiset = collections.Counter()

# Don't hide the bin builtin.
bin_ = 1
for i in xrange(n+k-1):
    if i in stars:
        multiset[bin_] += 1
    else:
        bin_ += 1

这将产生一个 collections.Counter 来计算每个数字被选中的次数。我已初始化 bin_ = 1 以生成 {1...n} 的多子集； bin_ = 0 将生成 {0...n-1} 的多子集。

(之前，我发布了一个建议使用多项式分布的答案。这不是正确的分布；它对具有重复元素的结果赋予的权重太小。对于错误，我们深表歉意。由于k星和n-1条的放置方式与{1...n}的多子集直接对应，此解应产生均匀分布。)