Tengo dos matrices de cadenas, no necesariamente de la misma longitud, quiero encontrar todos los "conjuntos" posibles de combinaciones entre dos valores de las matrices, sin repeticiones de ninguna de las matrices.
Por ejemplo, dados los arreglos:
{"A1", "A2", "A3"}
{"B1", "B2"}
El resultado que quiero es los siguientes conjuntos:
{("A1", "B1"), ("A2", "B2")}
{("A1", "B1"), ("A3", "B2")}
{("A1", "B2"), ("A2", "B1")}
{("A1", "B2"), ("A3", "B1")}
{("A2", "B1"), ("A3", "B2")}
{("A2", "B2"), ("A3", "B1")}

Mi dirección general es crear una función recursiva que tome como parámetro las dos matrices y elimine cada cadena "elegida" a la vez, llamándose a sí misma hasta que cualquiera de las matrices esté vacía, sin embargo, estoy un poco preocupado por los problemas de rendimiento (necesito ejecutar este código en aproximadamente 1000 pares de matrices de cadenas).
¿Alguien puede dirigirme hacia un método eficiente para hacer esto?