fengxx 最近的时间轴更新
fengxx

fengxx

V2EX 第 62748 号会员,加入于 2014-05-15 22:08:07 +08:00
fengxx 最近回复了
2014-05-15 22:53:52 +08:00
回复了 hourui 创建的主题 程序员 路径求解问题, 寻找算法大神指点
这个可以看成是一个 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
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2250 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 11ms · UTC 16:08 · PVG 00:08 · LAX 08:08 · JFK 11:08
Developed with CodeLauncher
♥ Do have faith in what you're doing.