Função para ler string e criar array com as combinações possíveis substituindo determinados elementos

Olá, sou iniciante em PHP. Estou com um problema na resolução de um exercício. Devo ler uma string que faça a substituição de determinados caracteres por números, criando um array com as combinações possíveis.

As regras são de substituição são:

X - Qualquer número de 0 a 9

Y -  Pode ser 1 ou 2

Z -  Qualquer número de 5 a 9

Por exemplo:

Entrada : X123

Saída: 0123, 1123, 2123, 3123, 4123, 5123, 6123, 7123, 8123, 9123

Entrada: Y12

Saída: 112, 212

Entrada: Y12Z

Saída: 1125, 2125, 1126, 2126, 1127, 2127, 1128, 2128, 1129, 2129

Entrada: XX

Saída: 00, 10, 20, 30, 40, 50, 60, 70, 80, 90, 01, 11, 21, 31, 41, 51, 61, 71, 81, 91, 02, 12, 32, 42, 52, 62, 72, 82, 92, etc...

Fiz o código monstrouso abaixo onde verifica

	se tem x, y e z;

	se tem x e y;

	se tem x e z;

	se tem y e z;

	se tem somente x;

	se tem somente y;

	se tem somente z.

<php?

$verif = strstr($str, "x");
$verif2 = strstr($str, "y");
$verif3 = strstr($str, "z");

if($verif and $verif2 and $verif3){
	for ($k=1; $k<=2; $k++){
 for ($j=5; $j<=9; $j++){
 for ($i = 0; $i <= 9; $i++){
 $teste = str_replace("x", "$i", $str);
 $teste2= str_replace("z", "$j", $teste);
 $teste3 = str_replace("y", "$k", $teste2);
 array_push($meuarray, $teste3);
 }
 }
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif and $verif2){
	for ($j=1; $j<=2; $j++){
 for ($i = 0; $i <= 9; $i++){
 $teste = str_replace("x", "$i", $str);
 $teste2 = str_replace("y", "$j", $teste);
 array_push($meuarray, $teste2);
 }
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif and $verif3){
	for ($j = 5; $j <= 9; $j++){
 for ($i = 0; $i <= 9; $i++){
 $teste = str_replace("x", "$i", $str);
 $teste2 = str_replace("z", "$j", $teste);
 array_push($meuarray, $teste2);
 }
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif2 and $verif3){
	for ($j = 1; $j <= 2; $j++){
 for ($i = 5; $i <= 9; $i++){
 $teste = str_replace("y", "$i", $str);
 $teste2 = str_replace("z", "$j", $teste);
 array_push($meuarray, $teste2);
 }
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif){
	for ($i = 0; $i <= 9; $i++){
 $teste = str_replace("x", "$i", $str);
 array_push($meuarray, $teste);
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif2){
	for ($i = 1; $i <= 2; $i++){
 $teste = str_replace("y", "$i", $str);
 array_push($meuarray, $teste);
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}

else if($verif3){
	for ($i = 5; $i <= 9; $i++){
 $teste = str_replace("z", "$i", $str);
 array_push($meuarray, $teste);
	}
	$arrayfinal = implode(",", $meuarray);
	echo $arrayfinal;
}
?>

	 

	Funciona para quando tiver apenas um caso de cada. Mas se houver dois x, três x, etc, não funcionará. Alguém poderia me ajudar?