按字典序输出一个字符串的全排序

题目描述

  输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

  大脑短路了，想明白这个竟然花了半小时。这个题目的核心其实是求解一个字符串的全排列。因为字典序只需要用
Collection.sort()方法排序一个ArrayList 或者TreeSet就行了。
 主要说下怎么对一个字符串进行全排列。比如说”abcd”怎么全排序呢?直觉告诉我们先把a放第一位，对”bcd”再进行全排列，就是一个递归。然后把b放在第一位，”acd”进行递归。…具体操作下面结合代码说。
 下面就是对全排列的字符串进行排序操作，按字典序输出即可。

代码实现

import java.util.ArrayList;
import java.util.Collections;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串
 * abc,acb,bac,bca,cab和cba。
 * 
 * 思路：先求解字符串的全排列，然后对这些全排列进行排序。
 * 
 * @author XIAO
 *
 */
public class StringPermutationSort {

	public ArrayList<String> Permutation(String str) {
		ArrayList<String> result = new ArrayList<>();// 保存全排列的结果
		if (str != null && str.length() > 0) {// 如果str不为空           
			Permutation(str.toCharArray(), 0, result);// 获取字符串的全排列  
		}
		Collections.sort(result);// 对全排列的字符串进行排序
		return result;
	}

	/**
	 * i 表示起始位置，从i这个位置开始向后寻找下面字符的全排列
	 * 
	 * @param charArray
	 * @param i
	 * @param result
	 */
	private void Permutation(char[] charArray, int i, ArrayList<String> result) {
		// 如果 i 是最后一个字符位置
		if (i == charArray.length - 1) {
			result.add(String.valueOf(charArray));// 找到一个全排序
		} else {
			for (int j = i; j <= charArray.length - 1; j++) {
				if (j != i && charArray[j] == charArray[i])// 有重复字符时，跳过
					continue;
				swap(charArray, i, j);
				Permutation(charArray, i + 1, result);
				swap(charArray, i, j);
			}
		}
	}

	// 交换字符数组s的第i个位置和第j个位置的字符
	private void swap(char[] s, int i, int j) {
		if (s[i] == s[j]) {
			;
		} else {
			char c = s[i];
			s[i] = s[j];
			s[j] = c;
		}
	}
}

  回头再看究竟是怎么全排列的吧。就是这个函数 private void Permutation(char[] charArray, int i, ArrayList result) 的递归过程。其中 i 表示起始位置，从i这个位置开始向后寻找下面字符的全排列。当i == charArray.length - 1 时，表示已经到了最后一个字符，那么就找到了一个全排列。下面很好看懂，就是递归向下找，但是为什么要交换两次 charArray i和j 位置的字符呢？
  其实拿”abcd”来说，当我们交换 a和b 的位置（第一次交换），然后用b作为首字符寻找全排列。但是下次我们要交换 a和c 的位置，但是这时候 a和b 已经交换了，所以要把 a和b 换回来，才能保证每次交换的顺序没有乱。