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