<?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'), | |
); |
<?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 | |
-------------- | |
*/ |
// | |
// 非递归的 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; | |
} |
<?php | |
$e = array( | |
array('a1', 'a2'), | |
array('b1', 'b2', 'b3', 'b4'), | |
array('c1', 'c2'), | |
); | |
$N = count($e); | |
$r = array(); | |
$n = array_fill(0, $N, 1); | |
for ($i = 1; $i < $N; $i++) | |
for ($j = $i; $j < $N; $j++) { | |
$cnt = count($e[$j]); | |
$n[$i - 1] *= $cnt; | |
} | |
$h = $n[0] * count($e[0]); | |
for ($i = 0; $i < $h; $i++) | |
for ($j = 0; $j < $N; $j++) { | |
$m = intval($i / $n[$j]) % (count($e[$j])); | |
$r[$i][$j] = $e[$j][$m]; | |
} | |
echo "n:", PHP_EOL, implode(" -> ", $n), PHP_EOL; | |
echo "res:", PHP_EOL; | |
foreach ($r as $v) echo implode(" -> ", $v), PHP_EOL; | |
/* | |
output: | |
-------------- | |
n: | |
8 -> 2 -> 1 | |
-------------- | |
res: | |
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 | |
-------------- | |
*/ |
#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 int h = 1; | |
static vector<int> n(N, 1); | |
static void init(vector<vector<string> > & v) | |
{ | |
for (int i = 0; i < N; i++) { | |
int n = e[i].n; h *= n; | |
const char ** s = e[i].s; | |
v.push_back(vector<string>(s, s + n)); | |
if (i) for (int j = i; j < N; j++) ::n[i - 1] *= e[j].n; | |
} | |
} | |
int main() | |
{ | |
vector <vector<string> > v; init(v); | |
vector <vector<string> > r(h, vector<string>(N, "")); | |
for (int i = 0; i < h; i++) | |
for (int j = 0; j < N; j++) r[i][j] = e[j].s[i / n[j] % e[j].n]; | |
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; | |
} |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <unistd.h> | |
#include <stdint.h> | |
#include <string.h> | |
static const char | |
*a[] = {"a1", "a2"}, | |
*b[] = {"b1", "b2", "b3", "b4"}, | |
*c[] = {"c1", "c2"}; | |
typedef struct { | |
const char **s; int n; | |
} vector; | |
static vector | |
e[] = { | |
{ a, sizeof(a) / sizeof(char *) }, | |
{ b, sizeof(b) / sizeof(char *) }, | |
{ c, sizeof(c) / sizeof(char *) } | |
}, | |
*r = NULL; | |
static const int N = sizeof(e) / sizeof(vector); | |
static int h = 1, n[N]; | |
static void init(void) | |
{ | |
for (int i = 0; i < N; i++) { | |
n[i] = 1; if (i) for (int j = i; j < N; j++) n[i - 1] *= e[j].n; | |
} | |
h = n[0] * e[0].n; | |
r = malloc(sizeof(vector) * h); | |
for (int i = 0; i < h; i++) { | |
r[i].n = N; | |
r[i].s = malloc(sizeof(char *) * N); | |
} | |
} | |
static void destroy(void) | |
{ | |
for (int i = 0; i < h; i++) free(r[i].s); | |
free(r); r = NULL; | |
} | |
int main() | |
{ | |
init(); | |
for (int i = 0; i < h; i++) | |
for (int j = 0; j < N; j++) r[i].s[j] = e[j].s[i / n[j] % e[j].n]; | |
for (size_t i = 0; i < h; i++) { | |
for (size_t j = 0; j < N; j++) { | |
if (j) printf(" -> "); | |
printf("%s", r[i].s[j]); | |
} | |
printf("\n"); | |
} | |
destroy(); | |
return 0; | |
} | |
![]() |
1
akfish 2014-05-15 01:58:21 +08:00
未细看,如果瓶颈仅仅在于内存的分配和释放的话,尝试一次性分配足够空间,反复重用。
|
![]() |
2
txx 2014-05-15 02:31:04 +08:00
數據規模是多大?
|
![]() |
3
davidli 2014-05-15 04:05:33 +08:00
既然是因为a的数量太多导致内存占用, 为什么不把a分割一下再分别处理呢
|
![]() |
4
iloahz 2014-05-15 07:31:33 +08:00
大概看了一遍,复杂度和空间都是理论下限了。到了常数阶段的话,可以试试:
1. 少用stl 2. 不要玩字符串,hash它 PS3. 个人觉得递归版很合理了,唯一是不要把数组当int玩啊。。 |
![]() |
5
exch4nge 2014-05-15 10:15:43 +08:00
|
![]() |
6
hourui OP |
![]() |
7
napoleonu 2014-05-15 11:47:54 +08:00
酷。
|
8
fengxx 2014-05-15 22:53:52 +08:00
这个可以看成是一个 Mixed radix numbers, 我们常用的是10进制数,比如3位以内的数字排列是0-999。如果是mixed radix 的话,可以看成第1位最大为X, 第2位最大为Y, 第3位为 Z, 那么所有的排列是
0 到 ZYX, 例如: 000 001 002 .... 00X 010 (这里产生了进位) 011 ... 01X 020(这里产生了进位) ..... .... 所有的排列之和为 X*Y*Z java code /** * * @author Ted */ public class MixedRadix { public void permutation(String[][] elements) { int[] mixedRadix = new int[elements.length + 1]; int[] number = new int[elements.length + 1]; //init for (int i = 0; i < elements.length; i++) { mixedRadix[i] = elements[i].length - 1; } //sentinel number[elements.length] = 1; int bits = 0; while (bits < elements.length) { printChoice(elements, number); int j = 0; while (number[j] == mixedRadix[j]) { number[j] = 0; j++; } number[j] = number[j] + 1; bits = j; } } private void printChoice(String[][] elements, int[] choice) { for (int i = 0; i < choice.length - 1; i++) { System.out.print(elements[i][choice[i]] + " "); } System.out.println(""); } public static void main(String... args) { String[][] elements = { {"a1", "a2"}, {"b1", "b2", "b3", "b4"}, {"c1", "c2"} }; MixedRadix mr = new MixedRadix(); mr.permutation(elements); } } 如果对这类问题感兴趣,可以参考 free book <Matters Computational> http://www.jjj.de/fxt/fxtpage.html#fxtbook |