Dadox número de matrices, cada una con un número de elementos posiblemente diferente, ¿cómo puedo recorrer todas las combinaciones donde selecciono un elemento de cada matriz?

Ejemplo:

[   ]   [   ]   [   ]
 foo     cat      1
 bar     dog      2
 baz              3
                  4

Devoluciones

[foo]   [cat]   [ 1 ]
[foo]   [cat]   [ 2 ]
  ...
[baz]   [dog]   [ 4 ]

Estoy haciendo esto en Perl, por cierto.