全排列

/**
 * 全排列,没有重复元素
 * @author gche
 * 思想：如求abc的全排列，可先求bc的全排列，bc,cb,然后分别和a进行组合成结果：abc,bac,bca,acb,cab,cba
 */
public class Arrange {


	@Test
	public void test(){
		String data = "abc";
		List<String> ret = this.arrange(data);
		System.out.println(ret.size() == size(data.length()));
		System.out.println(ret);
		Set<String> set = new HashSet<String>(ret);
		System.out.println(ret.size() == set.size());
	}

	/**
	 * 全排列
	 * @param str
	 * @return
	 */
	private List<String> arrange(String str){
		if(StringUtils.isEmpty(str)){
			return Collections.emptyList();
		}
		if(str.length() <= 1){
			return Arrays.asList(str);
		}
		//第一个字母和剩下字母的全排列组合
		return joint(str.charAt(0), arrange(str.substring(1)));
	}
	
	/**
	 * 组合。即<b>ch</b>插入到<b>arrs</b>
	 * 
	 * @param ch
	 * @param arrs
	 * @return
	 */
	private List<String> joint(char ch, List<String> arrs){
		List<String> ret = new ArrayList<String>((arrs.get(0).length()+1) * arrs.size());
		for(int i=0; i<arrs.size(); i++){
			String arr = arrs.get(i);
			for(int j=0; j<arr.length(); j++){
				ret.add(arr.substring(0, j) + ch + arr.substring(j));
			}
			ret.add(arr + ch);//last position
		}
		return ret;
	}

	/**
	 * 全排列的个数,验证
	 * @param i
	 * @return
	 */
	private int size(int i){
		if(i <= 1){
			return 1;
		}
		return i * size(--i);
	}
	
}