0

I have 3 sets of array each contains 12 elements of same type

a=[1 1 1 1 1 1 1 1 1 1 1];
b=[2 2 2 2 2 2 2 2 2 2 2];
c=[3 3 3 3 3 3 3 3 3 3 3];

I have to find how many ways it can be picked up if I need to pickup 12 items at a time

here, 1 1 2 is same as 2 1 1

I found this link Generating all combinations with repetition using MATLAB.

Ho this can be done in matlab within reasonable time.

is that way correct

abc=[a b c];
allcombs=nmultichoosek(abc,12);
combs=unique(allcombs,'rows');
Community
  • 1
  • 1
user38375
  • 31
  • 6
  • 3
    Does the linked solution not work for you? It appears to be doing exactly what you are asking for. – gariepy Jun 06 '16 at 19:00
  • For finding 12 solutions at a time taking indefinite time any wau out so that it could be done in reasonable time? what I am doing abc=[a b c]; allcombs=nmultichoosek(abc,12); combs=unique(allcombs,'rows'); is that way? – user38375 Jun 07 '16 at 03:03
  • Yes, finding all combinations will be computationally very very slow, if thats what you are asking. – Ander Biguri Jun 07 '16 at 08:40

1 Answers1

0

If you only need to find the number of ways to select the items, then using generating functions is a way to very efficiently compute that, even for fairly large values of N and k.

If you are not familiar with generating functions, you can read up on the math background here:

http://mathworld.wolfram.com/GeneratingFunction.html

and here:

http://math.arizona.edu/~faris/combinatoricsweb/generate.pdf

The solution hinges on the fact that the number of ways to choose k items from 36, with each of 3 items repeated 12 times, can be determined from the product of the generating function: 

g(x) = 1 + x + x^2 + x^3 + ... + x^12

with itself 3 times. The 12 comes from the fact the elements are repeated 12 times (NOT from the fact you are choosing 12), and multiplying by itself 3 times is because there are three different sets of elements. The number of ways to choose 12 elements is then just the coefficient of the power of x^12 in this product of polynomials (try it for smaller examples if you want to prove to yourself that it works).

The great thing about that is that MATLAB has a simple function conv for multiplying polynomials:

>> g = ones(1,13);  %% array of 13 ones, for a 12th degree polynomial with all `1` coefficents
>> prod = conv(g, conv(g, g));  %% multiply g by itself 3 times, as a polynomial
>> prod(13)
ans = 
     91

So there are 91 ways to select 12 elements from your list of 36. If you want to select 11 elements, that's z(12) = 78. If you want to select 13 elements, that's z(14) = 102.

Finally, if you had different numbers of elements in the sets, say 10 1's, 12 2's, and 14 3's, then you would have 3 distinct polynomials of the same form, 1 + x + x^2 + ..., with degrees 10, 12 and 14 respectively. Inspecting the coefficient of the degree k term again gives you the number of ways to choose k elements from this set.

gariepy
  • 3,576
  • 6
  • 21
  • 34