Program segment question for combinatorics

  • Thread starter Magenta55
  • Start date
  • #1
4
0

Main Question or Discussion Point

Consider the following segment where i,j,k,n and counter are integer variables and the value of n (a positive integer) is set prior to this segment.

counter := 0
for i := 1 to n do
for j :=1 1 to i do
for k :=1 to j do
counter := counter + 1

I am so lost as to what this program is even doing. Can anyone help explain what is does? I just need to know what it does upon first execution, second execution, etc.. and I may be able to solve it from there.
 

Answers and Replies

  • #2
phinds
Science Advisor
Insights Author
Gold Member
2019 Award
15,921
5,633
Consider the following segment where i,j,k,n and counter are integer variables and the value of n (a positive integer) is set prior to this segment.

counter := 0
for i := 1 to n do
for j :=1 1 to i do
for k :=1 to j do
counter := counter + 1

I am so lost as to what this program is even doing. Can anyone help explain what is does? I just need to know what it does upon first execution, second execution, etc.. and I may be able to solve it from there.
It's a simple nested loop that will end up with counter = j*i*n, which is a waste of time since you could just do the multiplication. Where nested loops are useful is where you DO something useful inside the loops, so I assume this is just an example of a nested loop for study purposes.

EDIT: OOPS ... no, that's NOT what it is. I see now that the inner loops are using the outer loop variables for a limit, SO ... this is something like a bubble sort nested loop and can be used for something LIKE(*) # of combinations or permutations. I'd have to look more closely to see how it might relate to combinatorial forumlae, but basically it's just a nested loop which, as I said, uses the outer loop variable as the inner loop limit.

(*) LIKE is emphasized to mean "not necessarily exactly" since I have not looked at the results in detail.
 
Last edited:
  • #3
300
22
This gives you ##{n+2 \choose 3}##. You have n+2 elements going from 1 to n+2. first you pick the element 2+i from range ##[3;n+2]##, then element 1+j from range ##[2;1+i]##, then k from ##[1;j]##. You are choosing all such possible combinations and by making the next choice in the range smaller than the last choice, you guarantee that you don't pick the same triple many times in a different order. The shifting starting point is necessary so that you have something to pick next, if you pick the first element at the first step, there wont be any left to pick in the next step, because in your formula the next index goes up to the previous one. So you are getting how many different triples can you take from n+2, which is the binomial coefficient ##{n+2 \choose 3}##.
 

Related Threads on Program segment question for combinatorics

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
124
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
3
Views
1K
Replies
1
Views
1K
Top