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,"");
}
}
分享到: