What is the name of this sequence generation problem? Any comments?

Question

I need to iterate over an ordered sequence that is defined by an array of numbers a_i, i = 1..n, where n is the length of each sequence element, and each a_i specifies the max number of possible values at position i in the output sequence.

Example:

• a = {10,10,10}
  Sequence: 000, 001, 002, ... 999 (the decimal numbers from 000 to 999)

• a = (2,3,2}
  Sequence: 000, 001, 010, 011, 020, 021, 100, 101, 110, 111, 120, 121

(Note: I don't just need to print the sequence, but I need to iterate over its elements, where each element is an array, e.g. {1,2,1}.)

Before I implement this, I wanted to ask if anyone has any comments? Maybe this is a known problem (name?), and there is already code available, or it reduces to some other well-known problem? It does have similarities to the permutation problem.

Answer 1

The elements of the sequences are listed in the lexographic order. Also see this (a different but related problem).

Answer 2

This is a Cartesian product.

In Python, itertools.product produces such lists of tuples.

>>> import itertools
>>> list(itertools.product(*map(range, [2, 3, 2])))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 0), (0, 2, 1),
 (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (1, 2, 0), (1, 2, 1)]

In other languages, it's easy to create a Cartesian product using nested loops:

for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
        for (int k = 0; k < 2; k++)
            cout << i << j << k << endl;

Answer 3

If you are using C# (linq) and the number of factors in the cartesian product is static, then it can also be quite elgantly expressed

    static void Main(string[] args)
    {
        IEnumerable<int> firstFactor = Enumerable.Range(0, 2);
        IEnumerable<int> secondFactor = Enumerable.Range(0, 3);

        var cartesianProd =
             from first in firstFactor
             from second in secondFactor
             select new { First = first, Second = second };

        foreach (var tuple in cartesianProd)
        {
            Console.WriteLine("({0}, {1})", tuple.First, tuple.Second);
        }
        Console.ReadLine();
    }