Mixing
Total number of iterations in $d$ nested for loops
Clash Royale CLAN TAG#URR8PPP
up vote
-2
down vote
favorite
Assume that there are $d$ number of for loops in a computer program. Let it be for example Matlab. A pseudo code will look like this:
for i=1:N
for j=i:N
for k=j:N
..
..
do something (costs one operation)
end
end
end
a. How many operations are performed altogether in terms of $N$ and $d$. Is there any formula for this?
b. Is there any way to write a computer program for example in Matlab, which will automatically create $d$ such for loops whenever the number $d$ is given?
Added: A combinatorics correspondance of the problem is the $d$-tuple combinations of numbers ranging from $1$ to $N$ without regarding the ordering. For example triple combinations of numbers from $1$ to $3$:
$(1,1,1),(1,1,2),(1,1,3)...(3,3,3)$ here we do not have the terms $(1,2,1)$ and $(2,1,1)$ because they are the same with $(1,1,2)$. The same goes to for example $(1,3,1)$ and $(3,1,1)$ etc.
combinatorics matlab programming
asked Jul 17 at 14:28
me me and me
63
 |Â
show 1 more comment
up vote
-2
down vote
favorite
Assume that there are $d$ number of for loops in a computer program. Let it be for example Matlab. A pseudo code will look like this:
for i=1:N
for j=i:N
for k=j:N
..
..
do something (costs one operation)
end
end
end
a. How many operations are performed altogether in terms of $N$ and $d$. Is there any formula for this?
b. Is there any way to write a computer program for example in Matlab, which will automatically create $d$ such for loops whenever the number $d$ is given?
Added: A combinatorics correspondance of the problem is the $d$-tuple combinations of numbers ranging from $1$ to $N$ without regarding the ordering. For example triple combinations of numbers from $1$ to $3$:
$(1,1,1),(1,1,2),(1,1,3)...(3,3,3)$ here we do not have the terms $(1,2,1)$ and $(2,1,1)$ because they are the same with $(1,1,2)$. The same goes to for example $(1,3,1)$ and $(3,1,1)$ etc.
combinatorics matlab programming
asked Jul 17 at 14:28
me me and me
63
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53
 |Â
show 1 more comment
up vote
-2
down vote
favorite
up vote
-2
down vote
favorite
Assume that there are $d$ number of for loops in a computer program. Let it be for example Matlab. A pseudo code will look like this:
for i=1:N
for j=i:N
for k=j:N
..
..
do something (costs one operation)
end
end
end
a. How many operations are performed altogether in terms of $N$ and $d$. Is there any formula for this?
b. Is there any way to write a computer program for example in Matlab, which will automatically create $d$ such for loops whenever the number $d$ is given?
Added: A combinatorics correspondance of the problem is the $d$-tuple combinations of numbers ranging from $1$ to $N$ without regarding the ordering. For example triple combinations of numbers from $1$ to $3$:
$(1,1,1),(1,1,2),(1,1,3)...(3,3,3)$ here we do not have the terms $(1,2,1)$ and $(2,1,1)$ because they are the same with $(1,1,2)$. The same goes to for example $(1,3,1)$ and $(3,1,1)$ etc.
combinatorics matlab programming
asked Jul 17 at 14:28
me me and me
63
Assume that there are $d$ number of for loops in a computer program. Let it be for example Matlab. A pseudo code will look like this:
for i=1:N
for j=i:N
for k=j:N
..
..
do something (costs one operation)
end
end
end
a. How many operations are performed altogether in terms of $N$ and $d$. Is there any formula for this?
b. Is there any way to write a computer program for example in Matlab, which will automatically create $d$ such for loops whenever the number $d$ is given?
Added: A combinatorics correspondance of the problem is the $d$-tuple combinations of numbers ranging from $1$ to $N$ without regarding the ordering. For example triple combinations of numbers from $1$ to $3$:
$(1,1,1),(1,1,2),(1,1,3)...(3,3,3)$ here we do not have the terms $(1,2,1)$ and $(2,1,1)$ because they are the same with $(1,1,2)$. The same goes to for example $(1,3,1)$ and $(3,1,1)$ etc.
combinatorics matlab programming
asked Jul 17 at 14:28
me me and me
63
edited Jul 17 at 15:41
asked Jul 17 at 14:28
me me and me
63
asked Jul 17 at 14:28
me me and me
63
asked Jul 17 at 14:28
me me and me
63
63
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53
 |Â
show 1 more comment
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient
$$binom Nd= fracN!(N-d)!cdot d!$$
The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d-1)$ to the values, meaning the result is
$$binom N+d-1d= frac(N+d-1)!(N-1)!cdot d!$$
You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.
answered Jul 17 at 15:36
Joffan
31.9k43169
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient
$$binom Nd= fracN!(N-d)!cdot d!$$
The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d-1)$ to the values, meaning the result is
$$binom N+d-1d= frac(N+d-1)!(N-1)!cdot d!$$
You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.
answered Jul 17 at 15:36
Joffan
31.9k43169
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
 |Â
show 1 more comment
up vote
1
down vote
accepted
If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient
$$binom Nd= fracN!(N-d)!cdot d!$$
The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d-1)$ to the values, meaning the result is
$$binom N+d-1d= frac(N+d-1)!(N-1)!cdot d!$$
You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.
answered Jul 17 at 15:36
Joffan
31.9k43169
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
 |Â
show 1 more comment
up vote
1
down vote
accepted
up vote
1
down vote
accepted
If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient
$$binom Nd= fracN!(N-d)!cdot d!$$
The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d-1)$ to the values, meaning the result is
$$binom N+d-1d= frac(N+d-1)!(N-1)!cdot d!$$
You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.
answered Jul 17 at 15:36
Joffan
31.9k43169
If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient
$$binom Nd= fracN!(N-d)!cdot d!$$
The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d-1)$ to the values, meaning the result is
$$binom N+d-1d= frac(N+d-1)!(N-1)!cdot d!$$
You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.
answered Jul 17 at 15:36
Joffan
31.9k43169
edited Jul 17 at 15:40
answered Jul 17 at 15:36
Joffan
31.9k43169
answered Jul 17 at 15:36
Joffan
31.9k43169
answered Jul 17 at 15:36
Joffan
31.9k43169
31.9k43169
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
 |Â
show 1 more comment
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
no. let $N=3$ and $d=3$, or ever worse let $N=3$ and $d=4$.
– me me and me
Jul 17 at 15:39
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
@memeandme slight misread of the question, corrected
– Joffan
Jul 17 at 15:40
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
okay the last one seems working. how did you get it?
– me me and me
Jul 17 at 15:45
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
Putting it the other way round to my answer, imagine choosing all increasing value $d$-tuples from $N+d-1$ options, then reducing each tuple by $(0,1,....,d-1)$, giving non-decreasing $d$-tuples from $N$. There are other ways to get to the same formula also.
– Joffan
Jul 17 at 15:48
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
i cannot upvote as I am under 15 years old
– me me and me
Jul 17 at 15:58
 |Â
show 1 more comment
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854549%2ftotal-number-of-iterations-in-d-nested-for-loops%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Negative voters, if this question is asked, please direct me to the source. I searched for a long time to find a similar question with no success. Probably I was not using the necessary keywords. This question corresponds to $d$-tuple combinations numbers from $1$ to $N$ without regarding the ordering. For example triple combinations and numbers from $1$ to $3$, then $(112)$ will appear only once because $(121)$ and $(211)$ are the same with $(112)$.
– me me and me
Jul 17 at 14:47
@Moo thanks for the comment. I can do it and get answers for some specific $N$ and $d$. There is no doubt for that. However, this problem is the same with a combinatorics problem as I tried to explain in my previous comment. Therefore this should already be known. There is a Matlab tag and therefore I thought maybe its okay to ask b here too. Btw, it doesnt matter if you downvoted because I have only $1$ points and happily enough Mathematics stack exhange doesnt allow negative points:)
– me me and me
Jul 17 at 14:52
@Moo you may ask why do I wann know this information a priori.. Because I would like to create a vector with zeros beforehand, so that my code will run without on the fly memory allocation, which will slow down everything..
– me me and me
Jul 17 at 14:54
I don't get why the question got so many downvotes? To me it looks fine...
– JuliusL33t
Jul 17 at 15:45
Yes, although there is a programming element that probably belongs elsewhere, there is also a mathematical question here. New user upvoted to reward engagement.
– Joffan
Jul 17 at 15:53