<?php
//
// 尾递归解法
//
$N = count($eg);

function go($step) {
  global $eg, $r, $N;
  if (!$step) {
    $r = array_map(function ($v) { 
      return array($v); 
    }, $eg[$step]);
  } else {
    $result = array();
    foreach ($r as $v)
    foreach ($eg[$step] as $ins) {
      $v[$step] = $ins;
      $result[] = $v;
    }
    $r = $result;
  }
  return ++$step < $N ? go($step) : true;
}

go(0);

foreach ($r as $v) echo implode(" -> ", $v), PHP_EOL;

/*
程序运行结果如下
--------------
a1 -> b1 -> c1
a1 -> b1 -> c2
a1 -> b2 -> c1
a1 -> b2 -> c2
a1 -> b3 -> c1
a1 -> b3 -> c2
a1 -> b4 -> c1
a1 -> b4 -> c2
a2 -> b1 -> c1
a2 -> b1 -> c2
a2 -> b2 -> c1
a2 -> b2 -> c2
a2 -> b3 -> c1
a2 -> b3 -> c2
a2 -> b4 -> c1
a2 -> b4 -> c2
--------------
*/