求助:字符串数组中字母的排列组合算法

Question

String[] s = {"A","BC","D","EF","G"}想要打印出这个字符串数组中字母的排列组合,效果向下面这样:
ABDEG
ABDFG
ACDEG
ACDFG请大家教教我,怎么循环或是递归.谢谢.

Answer 1

将String[] s = {"A","BC","D","EF","G"}构建成一个二叉树。第一层A 第二层有B，C 第三层都是D，第4层E，F第六层都是G，最后把每条路径遍历一遍就好了

Answer 2

public class 字符串的排列 {    static void test(ArrayList<String> al, String out) {
        if (al.isEmpty()) {
            System.out.println(out);
            return;
        } else {
            for (char c : al.remove(0).toCharArray()) {
                test((ArrayList<String>)al.clone(), out + c);
            }
        }
    }    public static void main(String[] args) {
        ArrayList<String> al = new ArrayList<String>();
        String[] s = {"A", "BC", "D", "EF", "G"};
        int i = 0;
        while (i < s.length) {
            al.add(s[i++]);
        }        test(al, "");
    }
}
主要就是吧不是一个字符的字符串循环一下就好了 写了一个递归的仅供参考

Answer 3

组合一类的问题，可以用模拟进位的方式来处理，不需要递归
class Test  {
    public static void main(String[] args) {
        String[] s = {"A","BC","D","EF","G"};
        char[][] c = new char[s.length][];
        int[] cnt = new int[s.length];
        int[] idx = new int[s.length]; //进位用计数器
        Arrays.fill(idx, 0); //初始为0
        for (int i=0; i<s.length; i++) {
            c[i] = s[i].toCharArray(); //把多个字符的字符串拆分为多个字符
            cnt[i] = c[i].length; //每个位置的字符数
        }
        
        while (true) {
            for (int i=0; i<idx.length; i++) {
                System.out.print(c[i][idx[i]]); //打印每个位置的字符
            }
            System.out.println();
            idx[idx.length-1]++; //最后一个位置计数器增加
            for (int i=idx.length-1; i>0; i--) { //判断是否发生进位
                if (idx[i]==cnt[i]) { //如果某一个位置的计数器达到该位置的最大字符数
                    idx[i]=0; //该位置的计数器清0
                    idx[i-1]++; //进位，也就是某位置的前一位递增
                }
            }
            if (idx[0]==cnt[0]) { //如果进位到头了，则退出while循环
                break;
            }
        }
        
    }
}

Answer 4

感谢楼上2位的给出的例子.看了qybao的回复后,我在想, 5楼zqfddqr给出的递归参考代码要比模拟进位的代码简洁不少,不知道这两者间会否有较大的性能差距? 如果性能或计算量上的差距可以忽略不计,为什么不用递归的方式解决呢?

Answer 5

递归可以简化代码，清晰思路，但是相对要牺牲性能。如果递归层数不深，感觉不出来，递归层数深，就有可能造成堆栈溢出。
所以递归和非递归在性能上还是有一定的差距的，就比如5L的代码，test((ArrayList<String>)al.clone(), out + c);每次递归本身就要新开一个函数栈，同时还要克隆一个list，消耗较多的内存。
如果不考虑性能上的差异，递归是个好选择，5L的代码还是不错的。