Лучший способ получить все комбинации корневого массива с другими n дочерними массивами

Я работаю над поиском путей и столкнулся с проблемами, с которыми мне нужна помощь. у меня есть
массив «корень», и мне нужно сравнить с другими массивами и найти все комбинации с каждым элементом «корень»

Единственный способ, которым я знаю, как это сделать, будет что-то вроде этого:

 function getAllCombinationsArray(){
$return = array();

$root = array( 1=>'cat1', 2=>'cat2', 3=>'cat3' );
$child_1 = array( 1=>'sub_cat1', 2=>'sub_cat2', 3=>'sub_cat3' );
$child_2 = array( 1=>'sub_sub_cat1', 2=>'sub_sub_cat2', 3=>'sub_sub_cat3' );

foreach($root as $fk => $fv){
foreach($child_1 as $ck => $cv){
$cid = $fk.'_'.$ck;
$cname = $fv.' -> '.$cv;
foreach($child_2 as $ck2 => $cv2){
$id = $cid.'_'.$ck2;
$name = $cname.' -> '.$cv2;
$return[$id] = $name;
}
}
}
return $return;
}

print_r(getAllCombinationsArray());

Выход:

Array
(
[1_1_1] => cat1 -> sub_cat1 -> sub_sub_cat1
[1_1_2] => cat1 -> sub_cat1 -> sub_sub_cat2
[1_1_3] => cat1 -> sub_cat1 -> sub_sub_cat3
[1_2_1] => cat1 -> sub_cat2 -> sub_sub_cat1
[1_2_2] => cat1 -> sub_cat2 -> sub_sub_cat2
[1_2_3] => cat1 -> sub_cat2 -> sub_sub_cat3
[1_3_1] => cat1 -> sub_cat3 -> sub_sub_cat1
[1_3_2] => cat1 -> sub_cat3 -> sub_sub_cat2
[1_3_3] => cat1 -> sub_cat3 -> sub_sub_cat3
[2_1_1] => cat2 -> sub_cat1 -> sub_sub_cat1
[2_1_2] => cat2 -> sub_cat1 -> sub_sub_cat2
[2_1_3] => cat2 -> sub_cat1 -> sub_sub_cat3
[2_2_1] => cat2 -> sub_cat2 -> sub_sub_cat1
[2_2_2] => cat2 -> sub_cat2 -> sub_sub_cat2
[2_2_3] => cat2 -> sub_cat2 -> sub_sub_cat3
[2_3_1] => cat2 -> sub_cat3 -> sub_sub_cat1
[2_3_2] => cat2 -> sub_cat3 -> sub_sub_cat2
[2_3_3] => cat2 -> sub_cat3 -> sub_sub_cat3
[3_1_1] => cat3 -> sub_cat1 -> sub_sub_cat1
[3_1_2] => cat3 -> sub_cat1 -> sub_sub_cat2
[3_1_3] => cat3 -> sub_cat1 -> sub_sub_cat3
[3_2_1] => cat3 -> sub_cat2 -> sub_sub_cat1
[3_2_2] => cat3 -> sub_cat2 -> sub_sub_cat2
[3_2_3] => cat3 -> sub_cat2 -> sub_sub_cat3
[3_3_1] => cat3 -> sub_cat3 -> sub_sub_cat1
[3_3_2] => cat3 -> sub_cat3 -> sub_sub_cat2
[3_3_3] => cat3 -> sub_cat3 -> sub_sub_cat3
)

Но это очень неэффективно, когда у меня есть несколько дочерних массивов с несколькими значениями.

Например.:

Если у меня есть один корневой массив с 3 элементами и 4 другими дочерними массивами с 1,36,21 и 2 элементами соответственно, то общее количество комбинаций будет 3 * 1 * 36 * 21 * 2 = 4536. Когда я выполняю вышеуказанную функцию, у меня жду больше 5 минут. Пожалуйста, я надеюсь, что вы поможете получить большую эффективность в моем алгоритме.