Math Question: Is it possible to calculate the row position as you loop through a cartesian product of two arrays?

Question

Is it possible to calculate the row position in the cartesian product of two arrays?

For example if you have one array of two rows and another of three rows it's easy to calculate the size of the cartesian product (Array1.Rows.Count * Array2.Rows.Count = 6), but you can't iterate through each array and just use the product of the respective row positions to calculate the row position in the cartesian product.

Array1.Row * Array2.Row
1 * 1 = 1
1 * 2 = 2
2 * 1 = 2
2 * 2 = 4
3 * 1 = 3
3 * 2 = 6

Is there a formula to obtain the result 1, 2, 3, 4, 5, 6 from Array1.Row and Array2.Row as you iterate through them in the following fashion:

For 1 To Array1.Rows.Count
    For 1 To Array2.Rows.Count
        'some formula here to obtain:'
        Cartesian.Row = Cartesian.Row + 1
    Next Array2.Row
Next Array1.Row

Thanks!

Answer 1

I'm not sure if I understand the question, but are you just asking for a simple 2D to 1D index transform?

If so, the formula is (for 1-based indexing)

FOR i1 = 1..N1 DO
  FOR i2 = 1..N2 DO
     (i1,i2) => ((i1-1) * N2) + i2)

Here's a Java snippet to demonstrate:

public class Carte {
    public static void main(String[] args) {
        count(1, 2);
        count(2, 1);
        count(3, 2);
    }   
    public static void count(final int N1, final int N2) {
        System.out.println(N1 + "x" + N2);
        for (int i1 = 1; i1 <= N1; i1++) {
            for (int i2 = 1; i2 <= N2; i2++) {
                System.out.format("(%d,%d)=%d%n", i1, i2, ((i1-1) * N2 + i2));
            }
        }
    }
}

This prints:

1x2
(1,1)=1
(1,2)=2
2x1
(1,1)=1
(2,1)=2
3x2
(1,1)=1
(1,2)=2
(2,1)=3
(2,2)=4
(3,1)=5
(3,2)=6

See also

• Row-major order