java 字符串的全排列输出

public class MyTestGameCore { 
public static void listAll(char[] arr_Str) { 
if (arr_Str.length <= 1) { 
System.out.println(arr_Str[0]); 
return; 
} 
doPerm(0 + 1, arr_Str, new char[] { arr_Str[0] }); 
} 

/* 
* index:当前要进行挨个插位的字符下标 arr_All:给定的字符数组 arr_Already:当前索引前已排好的字符数组 
*/ 
private static void doPerm(int index, char[] arr_All, char[] arr_Already) { 
if (index == arr_All.length - 1) { 
for (int i = index; i >= 0; i--) { 
System.out.println(new String(insertAt(arr_Already, i, 
arr_All[index]))); 
} 

} else { 
for (int i = index; i >= 0; i--) { 
doPerm(index + 1, arr_All, insertAt(arr_Already, i, 
arr_All[index])); 
} 
} 
} 

// 指定位置插入新的字符，并将原数组中的元素往后移动 
private static char[] insertAt(char[] char_Arr, int index, char c) { 
char[] tmp = new char[char_Arr.length + 1]; 
for (int i = 0, j = 0; i < tmp.length; i++, j++) { 
if (i == index) { 
tmp[index] = c; 
j--; 
} else { 
tmp[i] = char_Arr[j]; 
} 
} 
return tmp; 
} 

public static void main(String[] args) throws IOException { 
System.out.println("Please input a String!"); 
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
String str = br.readLine(); 

char[] arr_Str = str.toCharArray(); 
listAll(arr_Str); 

} 
} 

 

通过改变字符的插入位置，使用递归来实现全排列.

下面的代码是采用Set实现的全排列去重，原理与上面一样:

	public static Set<String> list(String str) {
		char[] array_all = str.toCharArray();
		if (array_all.length == 1) {
			System.out.println(array_all[0]);
			return null;
		}
		Set<String> set = new HashSet<String>();
		set = go(array_all, new char[] { array_all[0] }, 1);
		return set;
	}

	public static Set<String> go(char[] all, char[] already, int index) {
		Set<String> set = new HashSet<String>();
		if (index == all.length - 1) {
			for (int i = index; i >= 0; i--) {
				set.add(new String(insertINDEX(already,all[index],i)));
			}
		} else {
			for(int i = index; i >= 0; i--){
				set.addAll(go(all,insertINDEX(already,all[index],i),index+1));
			}
		}
		return set;
	}

	public static char[] insertINDEX(char[] already, char a, int index) {
		char[] temp = new char[already.length + 1];
		for (int i = 0 ,j= 0; i < temp.length;j++, i++) {
			if (i == index) {
				temp[i] = a;
				j = j - 1;
			} else {
				temp[i] = already[j];
			}
		}
		return temp;
	}
	
	public static void main(String [] args) throws IOException{
		System.out.println("Input A String!");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		Set<String> set = new HashSet<String>();
		set = list(str);
		Iterator it = set.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}
	}

 

评论

1 楼 longkeyy 2012-12-01  

如果这是全排列，那全组合是啥样？