Take all possible combinations for more than 15 elements

Hi all,

So I have an array A with 65 elements. I want to take sum of all possible 3 elements combination i.e.,

• Item one A1+A2+A3, A1+A2+A4, A1+A2+A5,...A1+A2+A65;
• Item one A1+A3+A4, A1+A3+A5, A1+A3+A6,...A1+A3+A65;and so on.How to do this?

Answer 1

[John D'Errico]

In most cases of this sort, the answer is: You need to spend the money to buy a big enough computer to solve the problem.

On this small problem, the answer is simple. Use nchoosek.

sum(A(nchoosek(1:65,3)),2)

Of course, then you will almost always come back and say that works for small problems, but what you really wanted to solve is how to do this when the vector has 10000 elements, and you want to take all possible sums of 5 elements, or 50. Then the answer will be: see my first comment. :)

[Shipra Jain]

Hi John, thanks for answering. You are right. Now I want to do the same thing for 2-65 elements. But I don't want to store the combinations actually. I just want to calculate the sum of each combination and then add the sum into a variable. Suppose there are 500 combination, then I want to add the sum of each combination to variable x and then later take average of x as x/500. Please help! Thanks :-)

[Shipra Jain]

And then I want to do the same thing not only for 3 elements, but 2,3,4...65 elements.

[John D'Errico]

Not storing the computations is irrelevant. You need to do the computations.

Re-read what I said.

"Of course, then you will almost always come back and say that works for small problems, but what you really wanted to solve is how to do this when..."

As I showed, it is trivial to do for combinations of 3 elements at a time. There are 43680 such combinations.

nchoosek(65,3)
ans =
       43680

However,

nchoosek(65,32)
Warning: Result may not be exact. Coefficient is greater than   9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
   3.6097e+18

Can you generate anything like 10^18 combinations of elements? It does not matter how you will do the sums. You need to make something on the order of 3.6e18 combinations. Oh, then if you will add them up, there will be 31 adds to do each sum. So roughly 1e20 floating point operations. 100 quintillion operations or so. Do you have a really fast computer? I hope so.

I figure, if your computer can do a billion adds per second, then the additions alone would take roughly 3.6 years to finish. Hey that is not too bad! Pick up a copy of something exciting like the Oxford English Dictionary, and read it through a few dozen times while you wait.

For some reason, people never seem to understand the limits of their computers. They see too many tv shows and movies, with computers that seem all powerful, capable of doing anything in a split second. In fact, it is trivial to define a problem that will take the lifetime of the universe (thus until it dies of heat death) to solve on a computer the size of the entire universe.

You need to decide if you REALLY need to do what you want. Then find a good way of avoiding exactly what you want to do.

[SHIPRA JAIN]

Hi John, Thanks for your answer.

Related to your question: "Do you have a really fast computer? I hope so."

-I do have one. It can do 10^14 operations per second. So I may need like, what, 2 seconds to do all this, right? I assume that's too less to go through even one page of Oxford dictionary.

I just wanted to know if this was doable in Matlab with standard processors or not? I get your point but there is no need to get so flustered and rude. For some reason, people never seem to understand the limits of their speech. Please stop lashing out at random people on open forums if you can't offer the solution to their problems.

Though you may think the problem I'm working on is "trivial" but it may be trivial for you, not for me. Since I DO need to solve it, I will anyway post it here. If you have a better way to do this, please help. If not, then also it's fine.

I have a matrix A with dimensions 14*65 and another matrix B with dimensions 14*1. I have to calculate the correlation coefficient between all possible combinations and B, for varying number of elements used for combination. For e.g.

For k=2 i.e taking combination of 2 elements at a time. So X will be an array of size 14*1, which is the average of all possible combinations with 2 elements using matrix A, then find pearson's correlation coefficient for X and B.

Similarly, for k=3, I need an array with all possible combination of 3 elements of A

And so on.

I want to know if this is doable or not. If not, then you can always to choose to write a simple "NO" rather than posting a story about universe, people, TV, oxford and what not!

Answer 2

[alice]

You can look at the nchoosek function:

doc nchoosek

Then you should be able to write something like this:

A = rand(65,1);
result = sum(nchoosek(A,3),1);

[John D'Errico]

The second argument to sum here would be 2, not 1. As you have written it, the answer will be a 1x3 vector, not the desired 43680x1 vector of sums.

[SHIPRA JAIN]

Thank you for your answer. But it is written that nchoosek is good for length(A)<15. In my case, A=65.

[Shipra Jain]

Sorry. I am referring to elements Alice. My element length is varying from 2-64. I have written only three as example. This function doesn't work beyond 15. What do I do. Please suggest.

Answer 3

[David Goodmanson]

Hello shipra,

If I understand this correctly, you want to find all possible combinations of the 65 elements of A taken 3 at a time, then sum each of those triples up and later take the average of all the sums. And then generalize that from 3 at a time to k at a time.

If A has n elements, then there are C(n,k) = nchoosek(n,k) = n!/((n-k)!k!) possibilities. Each of those brings in k elements of A, so the total number of occurrences of elements of A is C(n,k)*k. But by symmetry, each element of A is occurs the same number of times, so each element occurs C(n,k)*k/n times. The total of all the sums is C(n,k)*(k/n)*sum(A), and the mean over all C(n,k) possibilities is simply (k/n)*sum(A):

n = 65;
A = rand(1,n);

k = 4;
setofsums = sum(A(nchoosek(1:n,k)),2);
meansums = mean(setofsums)
sAkn = sum(A)*k/n
meanofsums = 1.7045
sAkn       = 1.7045

k = 64;
setofsums = sum(A(nchoosek(1:n,k)),2);
meansums = mean(setofsums)
sAkn = sum(A)*k/n

meanofsums = 29.9039
sAkn       = 29.9039

[SHIPRA JAIN]

Hi David,

Thanks for answer. But it doesn't work for k=35 and few more numbers in between. The problem is it exceeds the maximum permissible size/rows. I have posted the full problem in one of my comments on this thread. Please help in case you know how to do it.

Regards,

Shipra