已经知道16个字符,假设为:0123456789abcdef
求这16个字符组成的所有16位字符串，每个字符只出现一次。
总共有16！个的样子。
谁能给一个快速的方法？
------解决方案--------------------
public class TestString {
public static void g() {
char[] src = { '1', '2', 'a' };
g(src, new char[src.length], 0);
}
private static void g(char[] src, char[] result, int index) {
if (index >= src.length) {
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]);
System.out.print(" ");
}
System.out.println();
return;
}
for (int i = 0; i < result.length; i++) {
if (src[i] == 0) {
continue;
}
result[index] = src[i];
src[i] = 0;
g(src, result, index + 1);
src[i] = result[index];
}
}
public static void main(String arg[]) {
g();
}
}
//这是一个高手的全排序代码，好用的，测试数据太大会跑很久，就缩减了测试一下
------解决方案--------------------
求P16，这个要求不低啊，组合总共有：20,922,789,888,000，也是二十万亿，你需要怎样的算法才能算出所有的结果来？我个人觉得，基本可以放弃。
虽然如此，我还是用递归的方式来写了个简单算法，递归逻辑就是：N! = N * (N-1) ，代码如下：
- Java code
public class Permutation { public static void main(String[] args) { Character[] ps = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'}; long timer = System.currentTimeMillis(); int total = 0; total = fastPermutation(ps, 0); System.out.println("Got " + total + "\tspend: " + (System.currentTimeMillis() - timer) + "ms"); } public static int fastPermutation(Character[] ps, int pos) { int cnt = 0; if (pos < ps.length - 1) { fastPermutation(ps, pos + 1); for (int i = pos + 1; i < ps.length; i++) { swap(ps, pos, i); cnt += fastPermutation(ps, pos + 1); swap(ps, pos, i); } } else { cnt++; //System.out.println(Arrays.toString(ps)); // 打开输出的话，会比较浪费时间。 } return cnt; } private static void swap(Character[] ps, int pa, int pb) { Character tmp = ps[pa]; ps[pa] = ps[pb]; ps[pb] = tmp; }
------解决方案--------------------
写了个深搜。
暴力出所有情况。
但是，这是最不效率的方法。
应该有很高效的算法。
- Java code
public class Rank { private char[] rank; private boolean[] vist; private char[] c; private int size; public Rank(char[] c){ rank = new char[c.length]; vist = new boolean[c.length]; this.c = c; size = c.length; } public void showAllRank() { for (int i = 0; i < size; i++) { vist[i] = false; } dfs(0); } public void dfs(int level) { if (level == size) { for (int i = 0; i < size; i++) { System.out.print(rank[i]); } System.out.println(); } else { for (int i = 0; i < size; i++) { if ( !vist[i]) { vist[i] = true; rank[level] = c[i]; dfs(level+1); vist[i] = false; //回溯 } } } } }