<< Computer AlgorithmsUse  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