求一个快速排列出所有字符串组合的方法

Question

已经知道16个字符,假设为:0123456789abcdef 
求这16个字符组成的所有16位字符串，每个字符只出现一次。
总共有16！个的样子。
谁能给一个快速的方法？

Answer 1

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();
}}
//这是一个高手的全排序代码，好用的，测试数据太大会跑很久，就缩减了测试一下

Answer 2

求P16，这个要求不低啊，组合总共有：20,922,789,888,000，也是二十万亿，你需要怎样的算法才能算出所有的结果来？我个人觉得，基本可以放弃。虽然如此，我还是用递归的方式来写了个简单算法，递归逻辑就是：N! = N * (N-1) ，代码如下：
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;    }
P12，共计479,001,600（四亿七千九百万），耗时292731毫秒，差不多接近5分钟。

Answer 3

写了个深搜。
暴力出所有情况。
但是，这是最不效率的方法。应该有很高效的算法。
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; //回溯
}
}
}
}

}public class Test {
public static void main(String[] args) {
char[] c = { '0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
Rank r = new Rank(c);
r.showAllRank(); }

}

Answer 4

关键是要把代码弄出来，然后说服BOSS让他放弃。。

Answer 5

某BOSS语录：现在最快的电脑不是每秒运算几百亿次吗？区区几万亿次几分钟就算好了
唉。。

Answer 6

哦，让你BOSS把“天河II”租下来，然后把算法调整为支持云计算的，几分钟内还是有希望的。

Answer 7

另外二十万亿行，每行16个字符，大概还需要350TB的存储，让你BOSS也要租好。