>>621 を少し変えただけだが、

function foo($arr) {
$ret = array();
$keys = array_keys($arr);
$indices = array_flip($keys);
foreach ($keys as $key1) {
foreach ($keys as $key2) {
if ($indices[$key2] >= $indices[$key1]) {
break;
}
foreach ($arr[$key1] as $val1) {
foreach ($arr[$key2] as $val2) {
$ret[] = $val1 . $val2;
}
}
}
}
return $ret;
}