莫辂技术
今天是:
我需要三件东西:爱情友谊和图书。然而这三者之间何其相通!炽热的爱情可以充实图书的内容,图书又是人们最忠实的朋友。
User Image 获取一个字符串的所有组合 2019-05-04

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,"");
    }
}

 

45 likes - 2 comments

我的

类型标签

外部链接

网站访问总量