学步园

1 全排列

写一个函数, 如 angram(String str), 打印出 str 的全排列,如 abc 的全排列: abc, acb, bca,
dac, cab, cba

1.1 递归实现

为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归步骤如下：

1）确定第一个位置 ：第一个元素分别与后面元素交换

2）求后面位置的全排列

3）重复步骤1和2
4）递归结束条件：只有一个元素时，停止

	public void angram(String str){
		if(str==null)
			return;
		
		angram(str.toCharArray(),0);
	}//end angram()

private void angram(char[] a,int pBegin){
		//base case
		if(pBegin==a.length-1)
			display(a);
		else{
			//确定第一个位置
			for(int pCh=pBegin;pCh<a.length;pCh++){
					// swap pCh and pBegin
					swap(a,pBegin,pCh); //abc 交换后为 bac
					angram(a,pBegin++); //求bac的ac的全排列
					// restore pCh and pBegin
					swap(a,pBegin,pCh); //恢复bac为abc，继续a与abc的后续元素交换
			}//end for	
		}//end else
	} //end angram()

	private void swap(char[] a,int first,int change){
		char temp=a[first];
		a[first]=a[change];
		a[change]=temp;			
	}//end swap()
	
	private void display(char[] a){
		for(char c:a)
			System.out.print(c);	
		
		System.out.println();
	}//end display()

如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。

去掉重复的全排列由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。
换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

	private void angram(char[] a,int pBegin){
		//base case
		if(pBegin==a.length-1)
			display(a);
		else{
			//确定第一个位置
			for(int pCh=pBegin;pCh<a.length;pCh++){
				if(isSwap(a,pBegin,pCh)){ //在区间[pBegin,pCh]没有与pCh重复的字符才交换，以消除相同字符产生的相同排列结果
					// swap pCh and pBegin
					swap(a,pBegin,pCh); //abc 交换后为 bac
					angram(a,pBegin++); //求bac的ac的全排列
					// restore pCh and pBegin
					swap(a,pBegin,pCh); //恢复bac为abc，继续a与abc的后续元素交换
				}//end if
			}//end for	
		}//end else
	} //end angram()
	
	//在[pBegin,pEnd]区间中是否有字符与下标为pEnd的字符相等
	private boolean isSwap(char[] a,int pBegin,int pEnd){
		for(int pMove=pBegin;pMove<=pEnd;pMove++){
			if(a[pMove]==a[pEnd])
				return false;
		}//end for
		return true;
	}//end isSwap()

1.2  应用

2 组合

2.1 递归实现

2.2 应用