for loop running like a forever loop

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

Answer 1

[Matt J]

You could just use this.

[klb]

Thanks Matt. gave it a shot. rolling the question below to author of the code.

Answer 2

[John D'Errico]

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.

[klb]

Hi John. thanks for the code. ran it but, because it multiplies with the column number to obtain final answer, the possibility of 0 0 0 0 0 0 75 is eliminated. for my problem 75 0 0 0 0 0 0 is not same as 0 0 0 0 0 75 0.

[Bruno Luong]

If position matters the number of solutions is 324540216

[John D'Errico]

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]

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..