获取一个字符串的所有组合

1.获取一个字符串的所有组合，如：ABC,有ABC,ACB,BAC,BCA,CAB,CBA,如果考虑单个字符或少于字符串长度的组合则还有，A,B,C,AB,AC,BC,BA,CA,CB.

2.代码

public class StringPermutations<T> {

    public static Set permSet = new TreeSet<>();

    public static void permutation(String input){
         permutation("",input);
    }

    private static void permutation(String perm, String word) {
        if(word.isEmpty()){
            //System.out.println(perm+word);
            permSet.add(perm);
        }else{
            for(int noMore =0;noMore<=1;noMore++) {
                if(noMore==0) {
                    for (int i = 0; i < word.length(); i++) {
                        permutation(perm + word.charAt(i),
                                word.substring(0, i) + word.substring(i + 1, word.length()));
                    }
                }else{
                    permutation(perm,"");
                }
            }
        }
    }
}

3.测试

public class StringPermutationsTest {
    @Test
    public void permutiationTest(){
        StringPermutations.permutation("ABC");
        Set permSet = StringPermutations.permSet;
        permSet.forEach(System.out::println);
    }
}

output:

A
AB
ABC
AC
ACB
B
BA
BAC
BC
BCA
C
CA
CAB
CB
CBA

4,算法图

5.总结：对给出的字符串的第一个与其他的一次交换，然后递归调用，已固定的不在做交换。当然在有重复字符的时候，输出是有重复值的，

可以定义一个数组，如果有重复的，记录在改数组中，不做交换，如：

int a[] = new int[256];
for(int noMore =0;noMore<=1;noMore++) {
    if(noMore==0) {
        for (int i = 0; i < word.length(); i++) {
            if(a[word.charAt(i)]==0){
                a[word.charAt(i)]=1;
                repetPermutaion(perm + word.charAt(i),
                        word.substring(0, i) + word.substring(i + 1, word.length()));
            }
        }
    }else{
        repetPermutaion(perm,"");
    }
}