Geek Answers Handbook

Sample evenly from multiset

Given the many integers {1, ..., n}, I would like to selectively select from binomials {n + k-1} {k} different multisets of size k. Is there an effective way to do this?

For example, the set {1,2,3} has 6 multi-subsets of size 2. These are {1,2}, {2,3}, {1,3}, {1,1}, {2,2}, {3, 3}.

+4
source share
2 answers

Yes. Since you know that there are (n + k-1), select k such multisets, you probably know about the stars and columns of the combinatorial problem whose solution provides this formula. The solution to this problem involves a sampling procedure to create many subsets: randomly choose a method for placing k stars and n-1 bars, and then determine how the bands divide the stars into groups:

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

This will result in collections.Countercounting the number of times each number has been selected. I initialized bin_ = 1to create a multiset {1 ... n}; bin_ = 0will create a subset of {0 ... n-1}.

( , . , . . k n -1 {1... n}, .)

+2

, , :

import random as rd
#n,k - should be predefined
x=[[j]*k for j in xrange(n)] # [1,1,1,1 - k times, 2,2,2,- k times etc.]
rd.sample(x,k)
0

More articles:


All Articles