for loop running like a forever loop

1 次查看（过去 30 天）
klb
klb 2018-11-4
评论： klb 2018-11-7
Hi. Following generates combinations that sum to 75, using at least 2 values. This code runs but takes forever. How can i speed it?
counter = 75
i = 1;
for p = 0:counter-1
for q = 0:counter-1
for r = 0:counter-1
for s=0:counter-1
for t=0:counter-1
for u =0:counter-1
for v= 0:counter-1
x = [p q r s t u v];
if sum(x) == counter
usable(i,1:7) = x;
i = i + 1;
end
end
end
end
end
end
end
end

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

回答（2 个）

Matt J
Matt J 2018-11-4
You could just use this.
  1 个评论
klb
klb 2018-11-4
编辑：klb 2018-11-4
Thanks Matt. gave it a shot. rolling the question below to author of the code.

请先登录，再进行评论。

John D'Errico
John D'Errico 2018-11-4
编辑：John D'Errico 2018-11-4
Be serious. How many loops do you have here? How many passes? Is your computer infinitely large and fast?
counter = 75
But then you have 7 loops, nested, each of which run from 0 to counter-1.
75^7
ans =
1.3348e+13
So 13 trillion times though the inner part.
WORSE!!!!!! Inside those loops, you then dynamically grow an array.
All of which is done purely to find a sum of those 7 variables that equals 75.
So you are trying to compute all partitions of the number 75, at least using 7 or fewer numbers. Using a little tool I wrote many years ago, it looks like the number of partitions of 75 is:
numberOfPartitions(75)
ans =
8118264
So you are iteratively growing an array that may be as large as 8 million, searching through a search space that has size 13 trillion.
Are you even remotely surprised that this takes a HUGE amount of time?
First, DON'T GROW arrays dynamically. That is just a terrible idea, since MATLAB needs to reallocate that array each time through, copying the stuff already in that array over to the new array.
You might want to use a tool like my partitions function, found on the file exchange. This is a rather large set to generate, and don't hope that you can go much larger than 75. Well, lets say I don't know how large you want to go. The numbers will get large very fast.
https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer
For example, to solve your problem,
P = partitions(75,0:75,[],7);
size(P)
ans =
133939 76
Each row of P indicates one solution that was found.
P(1,:)
ans =
Columns 1 through 31
0 0 0 0 0 0 0 0 0 0 2 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Columns 32 through 62
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Columns 63 through 76
0 0 0 0 0 0 0 0 0 0 0 0 0 0
find(P(1,:))
ans =
11 12
Which tells us that
75 = 2*10 + 5*11 = 10 + 10 + 11 + 11 + 11 + 11 + 11
There were 133939 such distinct solutions found, in a few seconds of time on my computer.
  4 个评论
显示 2更早的评论
John D'Errico
John D'Errico 2018-11-7
Again, you need to consider that your computer has finite size and speed. There are often far better ways to solve a problem than brute force computing all possible solutions. But we are offered no clue as to why you are doing this.
klb
klb 2018-11-7
John, understood. That up there is portion of my real code. Loop works to iterations of 4 counter values (p,q,r,s) - all good there. Increase to 5 loop counters (p,q,r,s,t) and at that point it takes forever. I revisited the "big" problem statement and was able to reduce the sum requried to 63 and over 6 columns meaning 6 loop counters. (75 over 7 columns to 63 over 6 columns is coincidental, not correlated) Also, In the loops, i am already using counter-1 which means minimum 2 values are used to arrive at the total of now 63. that helps reduce no. of combinations. Does that help explain? i am still seeking an solution..

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by