[SciPy-user] Simple combinatorics with Numpy

Mico Filós elmico.filos@gmail....
Tue Oct 21 04:52:04 CDT 2008


I would like to use NumPy/SciPy to do some basic combinatorics on
small (size<6) 1D arrays of integers.

Imagine I have an array x=([1,3,5,8]) from which I draw, with replacement, a
sample of, say, 3 numbers. The ordering of the sample is unimportant. I want to
calculate the histogram of the averages of the samples (i.e., avg(1,1,1)=1,
avg(1,3,5)=3, etc). For that, I need to *enumerate* all the possible unordered
samples of size 3 that can be drawn from x, i.e.,

  (1,1,1), (1,1,3), (1,1,5), (1,1,8), (1,3,3), (1,5,5), ...
  [there are comb(4+3-1,3)=20 different samples]

and then, I need to compute, for each of them, the weight c/(4**3), where c is a
multinomial factor that takes into account possible repetitions of elements in
the sample.

Although I think I could come up with some dirty, inefficient lines of code
doing the job, I wonder whether there is any NumPy/SciPy function / trick that
could come in handy. I have seen that in Mathematica there is a function called
'Compositions(n,n)' that returns a list with all the possible arrangements of n
nonnegative integers that sum up n (e.g., Compositions(2,2) =
{(0,2),(1,1),(2,0)}). There is also a function 'KSubset' that returns all the
subsets of a given size that can be formed from a larger set. These function
are useful to generate all the possible samples. Is there anything similar in

Efficiency is not really an issue here, since the sets are always small. I am
aware that this is not the type of job NumPy is originally designed for, but
since the problem is simple and the implementation seems feasible (in
principle), I wanted to hear the opinion/hints of the experts on that. My
apologies if the answer turns out to be trivial.

Thanks for your attention.

More information about the SciPy-user mailing list