Take all possible combinations for more than 15 elements

3 次查看（过去 30 天）
SHIPRA JAIN
SHIPRA JAIN 2017-8-11
评论： SHIPRA JAIN 2017-8-16
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?

请先登录，再回答此问题。

回答（3 个）

John D'Errico
John D'Errico 2017-8-11
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. :)
  4 个评论
显示 2更早的评论
John D'Errico
John D'Errico 2017-8-13
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
SHIPRA JAIN 2017-8-16
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!

请先登录，再进行评论。

alice
alice 2017-8-11
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);
  3 个评论
显示 1更早的评论
SHIPRA JAIN
SHIPRA JAIN 2017-8-11
Thank you for your answer. But it is written that nchoosek is good for length(A)<15. In my case, A=65.
Shipra Jain
Shipra Jain 2017-8-11
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.

请先登录，再进行评论。

David Goodmanson
David Goodmanson 2017-8-13
编辑：David Goodmanson 2017-8-13
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
  1 个评论
SHIPRA JAIN
SHIPRA JAIN 2017-8-16
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Common Operations 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by