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 |