小弟有难，java排列组合问题，请各位朋友帮忙

Question

问题如下：char str={'a','b','c','d','e'}分别用1个、2个、3个、4个、5个'*'去不重复的替换字符我想得到类似下面的结果，每种我只列出一两个结果，
但是要将所有情况都列出，请问各位有什么好的实现方法，
具体的示例，谢谢各位高手，分不够再加 ：）
...1个
*bcde
a*cde
ab*de
...2个
**cde
a**de
a*c*e
...3个
***de
**c*e
...4个
****e
***d*
...5个
*****

Answer 1

treeroot(旗鲁特)对，要保证每个字母的位置是不变的即a永远在第1个，c永远在第3个，只是用*替换

Answer 2

纯组合问题，复杂度是 m^n，这里给出一个方法，但是如果数据量大的话基本上是算不出来的
    public static List getCompages(char[] chars,int num,char replace){
        
        if(chars.length==num){
            List ret=new ArrayList();
            ret.add(String.valueOf(chars));
            return ret;
        }
        if(num==1){
            List ret=new ArrayList();
            for(int i=0;i<chars.length;i++){
                char[] clone=(char[]) chars.clone();
                clone[i]=replace;
                ret.add(String.valueOf(clone));
            }
            return ret;
        }
        List ret=new ArrayList();
        
        //两种情况
        //第一个字符为替换符号
        char[] c1=new char[chars.length-1];
        System.arraycopy(chars,1,c1,0,c1.length);
        String s=""+replace;
        List list1=getCompages(c1,num-1,replace);
        for(int i=0;i<list1.size();i++){
            ret.add(s+(String)list1.get(i));
        }
        //第一个字符不是替换符号
        s=""+chars[0];
        List list2=getCompages(c1,num,replace);
        for(int i=0;i<list2.size();i++){
            ret.add(s+(String)list2.get(i));
        }        return ret;
    }

Answer 3

修正：
public static List getCompages(char[] chars,int num,char replace){
        
        if(chars.length==num){
            List ret=new ArrayList();
            char[] cs=new char[chars.length];
            Arrays.fill(cs,replace);
            ret.add(String.valueOf(cs));
            return ret;
        }
        if(num==1){
            List ret=new ArrayList();
            for(int i=0;i<chars.length;i++){
                char[] clone=(char[]) chars.clone();
                clone[i]=replace;
                ret.add(String.valueOf(clone));
            }
            return ret;
        }
        List ret=new ArrayList();
        
        //两种情况
        //第一个字符为替换符号
        char[] c1=new char[chars.length-1];
        System.arraycopy(chars,1,c1,0,c1.length);
        String s=""+replace;
        List list1=getCompages(c1,num-1,replace);
        for(int i=0;i<list1.size();i++){
            ret.add(s+(String)list1.get(i));
        }
        //第一个字符不是替换符号
        s=""+chars[0];
        List list2=getCompages(c1,num,replace);
        for(int i=0;i<list2.size();i++){
            ret.add(s+(String)list2.get(i));
        }        return ret;
    }

Answer 4

如果不需要考虑顺序，最好就是用位与做，复杂度 2^N int N = 3;
char[] ch = new char[N];
for(int i = 0; i < N; i++)
ch[i] = (char) ('a' + i);
for(int i = (int) (Math.pow(2, N)) - 1; i > 0; i--) {
for(int j = 0; j < N; j++) {
if((i >> (N - j - 1) & 1) == 0)
System.out.print(ch[j]);
else
System.out.print('*');
}
System.out.println();
}

Answer 5

呵呵，我来晚了。也贡献一个吧。
这段程序的设计思想是采用“递推”的算法，给定一个初始状态，然后推导出下一个状态，直到全部完成。public class C {    private int n;
    private String pattern;    public C(int n) {
        this.n = n;
        char[] s = new char[n];
        for (int i=0; i<n; i++) s[i] = (char)('a' + i);
        pattern = new String(s);
    }    public int enumerate(int m) {
        int r = 0;
        // p[] 保存着每个星号的位置
        int[] p = new int[m];
        // cp 表示下面要调整第几个星号的位置
        int cp = m-1;
        // 设置每个星号的初始位置
        for (int i=0; i<m; i++) p[i] = i;        // 根据星号当前的位置组合，得到下一个位置组合
        while (cp >= 0) {
            if (cp == m-1) {
                // 此时输出一个组合
                out(p);
                r ++;
            }            if (p[cp] < n-(m-cp)) {
                // 如果当前星号还有移动的空间，就移动一个位置
                p[cp]++;
                // 然后把它后面的星号重新排位
                while (cp < m-1) {
                    p[cp+1] = p[cp] + 1;
                    cp++;
                }
            } else {
                // 如果当前星号已经没有移动的空间，就尝试移动前一个星号
                cp --;
            }
        }
        return r;
    }    private void out(int[] p) {
        char[] a = pattern.toCharArray();
        for (int i=0; i<p.length; i++) a[p[i]] = '*';
        System.out.println(new String(a));
    }    public static void main(String[] args) {
        int N = 5;
        C worker = new C(N);
        for (int m=1; m<=N; m++) {
            int r = worker.enumerate(m);
            System.out.println("-- C (" + N + ", " + m + ") = " + r);
        }
    }}