Implement an arbitrary number N nested for loop

In my project, I'm looking for a way to create a nested for loop up to a fixed number N, for my purpose, the N is an integer smaller than 300, therefore it's useful to create such a function. To explain it better my problem, i would illustrate with an example:

list_to_loop = [1,a,b,c]

% Psuedo code:
for i in list_to_loop:
    for j in list_to_loop:
        for k in list_to_loop:
            Dosomething()
        end
    end
end

I guess you already see the logic behind, in this example N = 3, i.e. I get a 3 layer nested for loop. I have seen answers to similar questions before but the answers were not general enough or its not very easy to understand because i come from a python background. Is there a very simple and elegant way to do this?

[Bora Eryilmaz]

Having N nested for-loops, where "N is very big", is a very bad way of solving a problem (any problem). Could you find a different approach to solve your problem?

[DGM]

Since the function is not a function of the indices, then the nested loops are simply unnecessary. This is equivalent to the above.

list = [1 a b c]

for k = prod(list)
    % do thing
end

[Chun Tat]

@Bora Eryilmaz Thanks. Yes, I'm aware that N is big can consume the computer memory very quickly. I would like to run the code where N is not so big that the computer would take forever to run it. I'm interested in the case where N is not so big that I could still check if my approximated ansatz (truncated series) are close to the analytical solution.

[Bruno Luong]

"...fixed number N, for my purpose, the N is very big"

" I would like to run the code where N is not so big "

Please make up your mind.

And what exactly means "very big" and "not so big"? What typical size for each list? Please be more specific, or give us an example of input.

[Chun Tat]

@DGM Thank you, this was originally my approach to the problem, but the function i wanted to write depends on the indices, for simplicity, i did not specify it. I could write a (1+a+b+c)^N which returns all the possible combinations i want but this would take memory, therefore i was thinking about using a nested loop so the terms are sumed up during the for loop and it does not take much computer memory. I in fact knew how to do the nested forloop I want on python, i'm still new to matlab.

[Chun Tat]

@Bruno Luong Thanks for the comments. I will try to be more specific.The list will only contain 4 elements. And N can be as large as 100. Usually i run the code until my solution converges so it's hard to tell you exactly what N is.. but should be between 100-300.

Basically, I'm trying to compute all the possible combinations that can be given by the expansion of this expression

(1+a+b+c)^N where N can be anywhere as big as 100, for example N =3, it generates 1, 3a, 3a^2, a^3, 3b, 6ab, 3a^2 b, ... and so on. you can see this makes the list longer, and this takes a lot of memory as N gets bigger. I try to run a for-loop where a, b, c each variable corresponds to a sequence of multiplication operations applying on an input vector. This should avoid the need to save a long list of terms.

a = Mat A. Mat B

b = Mat A . Mat C . Mat D

c = Mat A. Mat E. Mat C. Mat D

and before i can do this i would like to see i can do

for i in [1,a,b,c]

for j in [1,a,b,c]

for k in [1,a,b,c]

print(i,j,k)

If memory wasn't an issue, i would first make a list of all the terms by expanding (1+a+b+c)^N

and loop over each of the item.

[Steven Lord]

The list will only contain 4 elements. And N can be as large as 100. Usually i run the code until my solution converges so it's hard to tell you exactly what N is.. but should be between 100-300.

Basically, I'm trying to compute all the possible combinations that can be given by the expansion of this expression

That's not going to happen with brute force. You want 100-300 loops each of which can take on 4 different values? How many times does the innermost body of that huge collection of loops get executed?

n = 4^100

n = 1.6069e+60

Let's say you could process a billion combinations a second. How long would it take you to process them all?

y = years(seconds(n/1e9))

y = 5.0922e+43

According to Wikipedia's Timeline of the far future you're going to have to wait until the Black Hole Era to get your results.

"Estimated time for all nucleons in the observable universe to decay, if the hypothesized proton half-life takes the largest possible value, 10^41 years,[8] assuming that the Big Bang was inflationary and that the same process that made baryons predominate over anti-baryons in the early Universe makes protons decay.[142][note 4] By this time, if protons do decay, the Black Hole Era, in which black holes are the only remaining celestial objects, begins.[136][8]"

[Chun Tat]

@Steven Lord I have found the solution to my question, yes the computation time scales up very quickly, this is why i am trying to truncate the expression I had. Thank you so much. And this is the solution I found, known as the "odometer" pattern

https://ch.mathworks.com/matlabcentral/answers/602395-different-number-of-for-loops#answer_502861

[Bruno Luong]

@Chun Tat ". And this is the solution I found, known as the "odometer" pattern"

I don't think you understood what we try to tell you.

"odometer" simply avoid to store all the combinations in the memory.

But it does speed up the calcultion and reduce the number of combination. You still have to wait unter universe reaches back-hole age to get your result.

[Walter Roberson]

The odometer pattern is not, in itself, "smart". It just tries all possibilities in sequence, without having to store the values, but it does not (without additional logic) have the ability to do short-cuts rejecting possibilities. If for example it turned out that the second coefficient needed to be 1 less than the first coefficient, then it would not be able to detect that immediately after changing the second coefficient, and would instead run through all possibilities for the 3rd to 100th coefficient before incrementing the second coefficient.

The odometer pattern is pure "brute force". it does not even try to optimize the search -- not without additional logic.

Answer 1

[Walter Roberson]

Is there a very simple and elegant way to do this?

No.

There are relatively compact methods involving ndgrid() and cell arrays, but for N = 100, you will run out of memory.

I have posted source code for generalized looping that has very low memory overhead (as long as you do not try to save all of the outputs); see https://www.mathworks.com/matlabcentral/answers/109622-how-can-i-write-n-for-loops-just-by-a-single-command#answer_118218 . In the comment there, the second version I link to is an iterator for the case where the different slots can have different numbers of entries and different data types.

[Chun Tat]

@Walter Roberson Thank you Walter Roberson, after reading the answers "odometer" pattern you gave to similar questions, i managed to get mine working!

Answer 2

[Bruno Luong]

Assuming a not so bug N of 100, and each of your list_to_loop has 2 elements, and you can compute 1000000000 (1e9) Dosomething() per second

You need

timeinyear = (2^100)/(1e9)/(3600*24*365)

timeinyear = 4.0197e+13

years to compute your nested loop. Still want to try?

[Chun Tat]

@Bruno Luong I'm fully aware of this problem but thank you for the comment.