<< Computer Algorithms Use  Ctrl +  or  –  to enlarge or reduce text size.

Variable Number of Nested Loops

Here is one  “For loop” going over a linear array of  n  points (i):
```For i = 1 To n
...
Next
```
Here are two For loops, nested one within the other, going over an  n x m  rectangular array of points (i, j):
```For i = 1 To n
For j = 1 To m
...
Next
Next
```
And three For loops with an eye toward more:
```For s1 = 1 To n1
For s2 = 1 To n2
For s3 = 1 To n3
...
Next
Next
Next
```
And so on.  In each case the number of loops – the dimension of the array – is “hardwired in.”  You know how many loops are needed when you write the program.  But suppose you don’t know beforehand how many loops – how many s1, s2, s3, etc. – will be needed. How could you have a variable number of loops, programmatically variable?

One way to do it would be to call a subroutine, containing just one loop, recursively, and have a global variable keep track of the current level.  The recursive method is demonstrated at the end of this article.  However the problem can be solved without recursion. There is a way to replace any number, unknown in advance, of For loops with just two loops. The number of loops it simulates is a variable.

Call the number of loops d. In the following code the indices are s(1), s(2), ... up to s(d). The width of each range can depend on d, say nt(d). The range starts at 1; comments in the code show how to make it start at 0, or from a variable depending on d, say it(d), instead of a fixed number.  The code is written for PBCC  and can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.
```Function PBMain
Local d As Long         'dimension of box
Local s() As Long       'element of box
Local v As Long         'index into s()
Local u As Long         'index into elements of box
Local k As Long         'total number of box elements
Local slice() As Long   'pre-computed products

d = 4                            '<-- 4 dimensional box, change to suit
Dim nt(1 To d) As Long
Dim slice(d)
Dim s(d - 1)

Array Assign nt() = 3, 4, 5, 2   '<-- 3×4×5×2 box, change to suit

Print "This is a ";
For k = 1 To d
Print Format\$(nt(k)); :If k < d Then Print "x";
Next
Print " box:" :Print

' Pre-compute running product of the dimensions.
slice(0) = 1
For u = 1 To d
slice(u) = slice(u - 1) * nt(u)
Next

k = slice(d)

' We could make the inner For go to d - 1 like this
'  For u = 0 To k - 1
'   For v = 0 To d - 1
'    s(v) = 1 + (u Mod slice(v + 1)) \ slice(v)
'    ...
'   Next
'   Print
'  Next
' But the d - 1 case doesn't need the Mod.

For u = 0 To k - 1
For v = 0 To d - 2
s(v) = 1 + (u Mod slice(v + 1)) \ slice(v)
' Here's where you do what you want with the s(),
' in this demo we just print them out.
Print s(v);
Next
s(v) = 1 + u \ slice(v)
Print s(v)
Next

' If you want the indices to start at 0 instead of 1,
' and still range over nt values (that is, end at nt - 1),
' just remove the "1 +" in "s(v) = 1 + ..." (two places).

' You can have the indices start at a variable number,
' called say it(), just replace the first 1 with it(v)
' and the second with it(d - 1).  The size of the box
' will remain nt(), that is, go from it() to nt() + it() - 1.

Print
Print "Use the scrollbar at right to see the whole list."
WaitKey\$
End Function
```

If each range is the same, making a cubical box, the code can be simplified:
```Function PBMain
Local d As Long         'dimension of box
Local n As Long         'side of d-dimensional box
Local s() As Long       'element of box
Local v As Long         'index into s()
Local u As Long         'index into elements of box
Local k As Long         'total number of box elements
Local np() As Long

d = 3                          '<-- change to suit
ReDim np(d)
ReDim s(d - 1)

n = 5           '5 x 5 x 5      <-- change to suit

Print "This is a ";
For k = 1 To d
Print Format\$(n); :If k < d Then Print "x";
Next
Print " box:" :Print

' Set up powers of d.
For u = 0 To d
np(u)  = n ^ u
Next

k = np(d)

' We could make the inner For go to d - 1 like
' For u = 0 To k - 1
'  For v = 0 To d - 1
'   s(v) = (u Mod np(v + 1)) \ np(v)
'   ...
'  Next
'  print
' Next
' But the d - 1 case doesn't need the Mod.

For u = 0 To k - 1
For v = 1 To d - 1
s(v) = 1 + (u Mod np(v)) \ np(v - 1)
Print s(v);" ";
Next
s(v) = 1 + u \ np(v - 1)
Print s(v)
Next

Print
Print "Use scrollbar at right to see entire list."
WaitKey\$
End Function
```

If the range width n is a power of two, the code can be simplified further:
```Function PBMain
Local d As Long         'dimension of box
Local n As Long         'side of d-dimensional box
Local s() As Long       'element of box
Local v As Long         'index into s()
Local u As Long         'index into elements of box
Local k As Long         'total number of box elements
Local np() As Long
Local np1() As Long

d = 3                         '<-- change to suit
ReDim np(d)
ReDim np1(d)
ReDim s(d - 1)

' n is asumed to be a power of 2
n = 4           '4 x 4 x 4    '<-- change to suit

Print "This is a ";
For k = 1 To d
Print Format\$(n); :If k < d Then Print "x";
Next
Print " box:" :Print

' Set up powers of d.
For u = 0 To d
np(u)  = n ^ u
np1(u) = n ^ u - 1
Next

k = np(d)

' Since n is a power of 2, all its powers are,
' and we can use the formula
' u Mod pn(k) = (u and pn1(k))
For u = 0 To k - 1
For v = 0 To d - 2
s(v) = 1 + (u And np1(v + 1)) \ np(v)
Print s(v);
Next
s(v) = 1 + u \ np(v)
Print s(v)
Next

Print
Print "Use scrollbar at right to see entire list."
WaitKey\$
End Function
```

If you want to use recursion to solve the problem (shorter code but slower):
```Global d As Long
Global nt() As Long
Global row() As Long

Function NestedLoop(level As Long) As Long    'this function is never given a value
Local i As Long
If level > d Then
For i = 1 To d
Print row(i);
Next
Print
Exit Function
End If
For i = 1 To nt(level)
row(level) = i
NestedLoop (level + 1)               'recursive call
Next
End Function

Function PBMain
d = 4                                  '<-- 4 dimensional box, change to suit
Dim nt(1 To d) As Long
Dim row(1 To d) As Long
Array Assign nt() = 3, 4, 5, 2         '<-- 3×4×5×2 box, change to suit
NestedLoop 1                           'start at level 1
WaitKey\$
End Function
```

If you want the dimensions cycled first to last as before:
```Global d As Long
Global nt() As Long
Global row() As Long

Function NestedLoop(level As Long) As Long    'this function is never given a value
Local i As Long
If level < 1 Then
For i = 1 To d
Print row(i);
Next
Print
Exit Function
End If
For i = 1 To nt(level)
row(level) = i
NestedLoop (level - 1)               'recursive call
Next
End Function

Function PBMain
d = 4                                  '<-- 4 dimensional box, change to suit
Dim nt(1 To d) As Long
Dim row(1 To d) As Long
Array Assign nt() = 3, 4, 5, 2         '<-- 3×4×5×2 box, change to suit
NestedLoop d                           'start at level d
WaitKey\$
End Function
```