Iterating Over Dynamic Number of Nested Loops

Introduction

Sometimes, you need to iterate over an unknown number of for or foreach loops. For example, let's say we have the following collection of collections of strings:

var data = new List<List<string>>{
    new List<string>{"red", "green", "blue"},
    new List<string>{"apple", "banana", "peach", "mellon"},
    new List<string>{"one", "two"}
};

And we need to generate the following sequence (all possible ordered combinations):

• red-apple-one
• red-apple-two
• red-banana-one
• red-banana-two
• red-peach-one
• red-peach-two
• red-mellon-one
• red-mellon-two
• green-apple-one
• green-apple-two
• green-banana-one
• green-banana-two
• green-peach-one
• green-peach-two
• green-mellon-one
• green-mellon-two
• blue-apple-one
• blue-apple-two
• blue-banana-one
• blue-banana-two
• blue-peach-one
• blue-peach-two
• blue-mellon-one
• blue-mellon-two

This can be achieved by the following C# code:

for(var x = 0; x < data[0].Count; x++)
    for(var y = 0; y < data[1].Count; y++)
        for(var z = 0; z < data[2].Count; z++)
            Console.WriteLine("{0}-{1}-{2}", data[0][x], data[1][y], data[2][z]);

As you can see, we had to execute 3 nested loops in order to access information we need. What if the data collection had more sub-collections? We would have to code as many nested loops as many sub-collections contained in the parent data collection. Below is an example that addresses this issue and allows iterating over any number of nested sub-collections producing the same result as shown above.

Solution

The idea is to maintain 2 arrays of integers (bounds and counters) of size N, where N is the number of nested collections. The bounds array will be populated with sizes of all nested collections while the counters array will be initialized with zeros and will represent current state (iteration indexes) of all nested loops. In the while loop, we will keep incrementing the counter at loopIndex position till it hits the bound. When the bound is hit, we will increment adjacent counter (loopIndex - 1) while setting current one to zero to start it over, and so on.

C# Implementation

private static void Main()
{
    var data = new List<List<string>>
    {
        new List<string> {"red", "green", "blue"},
        new List<string> {"apple", "banana", "peach", "mellon"},
        new List<string> {"one", "two"}
    };

    foreach (var item in IterateDynamicLoop(data).Select(x => string.Join("-", x)))
        Console.WriteLine(item);

    Console.ReadLine();
}

public static IEnumerable<IEnumerable<T>> IterateDynamicLoop<T>(IList<List<T>> data)
{
    var count = data.Count;

    var loopIndex = count - 1;
    var counters = new int[count];
    var bounds = data.Select(x => x.Count).ToArray();

    do
    {
        yield return Enumerable.Range(0, count).Select(x => data[x][counters[x]]);
    } while (IncrementLoopState(counters, bounds, ref loopIndex));
}

private static bool IncrementLoopState(IList<int> counters, IList<int> bounds, ref int loopIndex)
{
    if (loopIndex < 0)
        return false;

    counters[loopIndex] = counters[loopIndex] + 1;

    var result = true;

    if (counters[loopIndex] >= bounds[loopIndex])
    {
        counters[loopIndex] = 0;
        loopIndex--;
        result = IncrementLoopState(counters, bounds, ref loopIndex);
        loopIndex++;
    }

    return result;
}

Delphi Implementation

program DynamicLoopDemo;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes, Variants;

type
  TDynStringArray = array of string;

function IncrementLoopState(var ACounters, ABounds: array of Integer; var ALoopIndex: Integer): Boolean;
begin
  Result := False;
  if ALoopIndex < 0 then
    Exit;

  ACounters[ALoopIndex] := ACounters[ALoopIndex] + 1;

  if ACounters[ALoopIndex] >= ABounds[ALoopIndex] then
  begin
    ACounters[ALoopIndex] := 0;
    Dec(ALoopIndex);
    Result := IncrementLoopState(ACounters, ABounds, ALoopIndex);
    Inc(ALoopIndex);
  end
  else
    Result := True;
end;

procedure IterateDynamicLoop(AList: TStrings; AData: Variant);
var
  I, lMaxCount, lLoopIndex: Integer;
  lCounters, lBounds: array of Integer;
  lItem: string;
begin
  lMaxCount := VarArrayHighBound(AData, 1) + 1;
  lLoopIndex := lMaxCount - 1;
  SetLength(lCounters, lMaxCount);
  SetLength(lBounds, lMaxCount);

  for I := 0 to lMaxCount - 1 do
  begin
    lCounters[I] := 0;
    lBounds[I] := VarArrayHighBound(AData[I], 1) + 1;
  end;

  repeat
    lItem := '';
    for I := VarArrayLowBound(AData, 1) to VarArrayHighBound(AData, 1) do
    begin
      if lItem <> '' then
        lItem := lItem + '-';
      lItem := lItem + AData[I][lCounters[I]];
    end;
    AList.Add(lItem);
  until not IncrementLoopState(lCounters, lBounds, lLoopIndex);
end;

procedure RunDemo;
var
  lData: Variant;
  lList: TStrings;
  I: Integer;
begin
  lData := VarArrayOf([
    VarArrayOf(['red', 'green', 'blue']),
    VarArrayOf(['apple', 'banana', 'peach', 'mellon']),
    VarArrayOf(['one', 'two'])]);

  lList := TStringList.Create;
  try
    IterateDynamicLoop(lList, lData);
    for I := 0 to lList.Count - 1 do
      WriteLn(lList[I]);
  finally
    lList.Free;
  end;
end;

begin
  RunDemo;
  ReadLn;
end.