Tengo la siguiente matriz que contiene matrices de valores:

$array = array(
    array('1', '2'),
    array('a', 'b', 'c'),
    array('x', 'y'),
);

Puede haber cualquier número de matrices y una matriz puede contener cualquier número de valores. Actualmente tengo un fragmento de código que generará todas las combinaciones donde se toma un valor de cada matriz. p.ej:

1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy

Sin embargo, lo que realmente quiero es solo las combinaciones donde solo hay un valor en cada columna, es decir. 1ax no es bueno porque los tres valores 1, a y x están en la primera columna, 1by no es bueno porque b y y están en la segunda columna. Entonces, del ejemplo anterior, solo estas combinaciones serían válidas:

1cy, 2cx

Originalmente planeé generar todas las combinaciones y luego filtrar aquellas con conflictos, pero eso no se puede escalar, ya que este es un ejemplo simplificado, en la aplicación real habrá situaciones en las que potencialmente hay millones de combinaciones (incluidas las conflictivas). ).

¿Alguien puede ayudar con una mejor manera de resolver esto? Estoy trabajando en PHP, pero cualquier ejemplo de código que demuestre claramente la lógica sería útil.

Gracias por adelantado.

Actualizar:

He probado las soluciones que funcionan contra un conjunto de datos más grande, para obtener algunos puntos de referencia, estos son los resultados hasta ahora:

$array = array(
    array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'),
    array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
    array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'),
    array('1', '2', '3', '1', '2', '3', '1', '2', '3'),
    array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
    array('x', 'y', 'z'),
);

Josh Davis 2ª solución:

Combinations:      249480
Time:              0.3180251121521 secs
Memory Usage:      22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb

Josh Davis:

Combinations:      249480
Time:              1.1172790527344 secs
Memory Usage:      22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb

Tom Haigh:

Combinations:      249480
Time:              5.7098741531372 secs
Memory Usage:      39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb