路径求解问题, 寻找算法大神指点

[hourui]

今天做项目遇到了一个棘手的问题, 整理归纳以后大致总结为是一个路径求解问题
问题如下, 以及经过无数脑细胞过度死亡后, 粗略的尾递归解法一并给出

由于项目是c++的(转换为php仅是为了方便大家阅读)
此法会导致大量的内存分配和释放, 效率并不是很高!
想问下v2上的算法大神, 有无更高效的解决方案?

昨天和基友@napoleonu 思索到深夜...
找到了一种「矩阵法」求解方式, 简单理解为把结果想象为一个矩阵, 然后做填空题
代码实现如下:

欢迎各路大神交流

[akfish]

未细看，如果瓶颈仅仅在于内存的分配和释放的话，尝试一次性分配足够空间，反复重用。

[txx]

數據規模是多大？

[davidli]

既然是因为a的数量太多导致内存占用， 为什么不把a分割一下再分别处理呢

[iloahz]

大概看了一遍，复杂度和空间都是理论下限了。到了常数阶段的话，可以试试：

1. 少用stl
2. 不要玩字符串，hash它
PS3. 个人觉得递归版很合理了，唯一是不要把数组当int玩啊。。

[exch4nge]

字符串上的消耗比较大吧，基本同意 @iloahz 的。
话说为什么用递归（尾递归）？不是直接可以嵌套循环么？
尾递归如果编译器没优化的话，不是因为push/pop stack的原因效率会更慢么？

[hourui]

@akfish 数据宽度和深度都是未知, 所以无法预估空间消耗...
@txx 这是跑在一个在线engine上的, 对于性能要求很高, 由于每次轮询都需要重新构建vector, 数据膨胀造成的性能下降不是线性的... 所以我觉得这不是最优解...
@iloahz 为了方便理解, 直接写成string了, 实际项目中已经做过一次onway hash, string的频繁构建析构是不存在的
@exch4nge 你可以看下c++的版本, 是一个循环解法, 是php版本尾递归的非递归实现

[napoleonu]

酷。

[fengxx]

这个可以看成是一个 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

[hourui]

@fengxx 「Mixed radix numbers」这个思路赞. 谢谢指点