A->B路径求解问题

1.Q.php

<?php

// --------------------------------------
//              通往
// 假设 [begin]  ->  [end] 之间有 N 个step
// 每个 step.i 又有 iM 个节点
// 需要求解 [begin] -> [end] 所有路径组合
// --------------------------------------


// ----
// 示例
// ----
$eg = array(                     // --------
	                         // [begin]
  array('a1', 'a2' /* ...aM */), // step.1
  array('b1', 'b2', 'b3', 'b4'), // step.2
  array('c1', 'c2')              // step.3
	                         // ...
                                 // step.N
	                         // [end]
);                               // -------

// -----------------------------------------------
// 求解 step.1 -> step.2 -> step.3 [-> ... step.N]
// 所有路径组合 
// -----------------------------------------------

// -------
// 预期结果
// -------
$result = array(
  array('a1', 'b1', 'c1'),
  array('a1', 'b1', 'c2'),
  array('a1', 'b2', 'c1'),
  array('a1', 'b2', 'c2'),
  array('a1', 'b3', 'c1'),
  array('a1', 'b3', 'c2'),
  array('a1', 'b4', 'c1'),
  array('a1', 'b4', 'c2'),
  array('a2', 'b1', 'c1'),
  array('a2', 'b1', 'c2'),
  array('a2', 'b2', 'c1'),
  array('a2', 'b2', 'c2'),
  array('a2', 'b3', 'c1'),
  array('a2', 'b3', 'c2'),
  array('a2', 'b4', 'c1'),
  array('a2', 'b4', 'c2'),
);

2.A.php

<?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
--------------
*/

3.A.cc

//
// 非递归的 c++ stl 实现版本
//
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stdint.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

static const char 
*a[] = {"a1", "a2"},
*b[] = {"b1", "b2", "b3", "b4"},
*c[] = {"c1", "c2"};


static const struct {
  const char **s; int n;
} e[] = {
  { a, sizeof(a) / sizeof(char *) },
  { b, sizeof(b) / sizeof(char *) },
  { c, sizeof(c) / sizeof(char *) }
};

static const int N = 3;

static void init(vector<vector<string> > & v) 
{
  for (int i = 0; i < N; i++) {
    const char ** s = e[i].s;
    v.push_back(vector<string>(s, s + e[i].n));
  }
}

static void multi(vector<vector<string> > & r, vector<string> & v)
{
  vector<string>            item;
  vector<vector<string> > result;
  for (size_t i = 0; i < r.size(); i++) {
    vector<string>(r[i]).swap(item);
    item.push_back("");
    for (size_t j = 0; j < v.size(); j++) {
      item[item.size() - 1] = v[j];
      result.push_back(item);
    }
  }
  result.swap(r);
}

int main() 
{
  vector <vector<string> > v, r; init(v);
  vector<string> first(*v.begin());

  for (size_t i = 0; i < first.size(); i++)
  r.push_back(vector<string>(1, first[i]));

  for (size_t i = 1; i < v.size(); i++) multi(r, v[i]);
  for (size_t i = 0; i < r.size(); i++) {
    for (size_t j = 0; j < r[i].size(); j++) {
      if (j) printf(" -> ");
      printf("%s", r[i][j].c_str());
    }
    printf("\n");
  }  

  return 0;
}