全排列之字典序法

(1) 對於輸入的字典序排列，反向查找第一對滿足a[j] (2) 仍舊反向查找第一個下標k，使得 a[j] (3) 交換a[j]和a[k]
(4) 翻轉a[j+1]~a[end]

此法能適應有重復元素的系列

代碼如下：

#include 
#include 

using namespace std;

int cmp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

inline void println(int arr[], int len){
	for(int i = 0; i < len; i++){
		cout << arr[i] << " ";
	}
	cout << endl;
}
inline void reverse(int arr[], int left, int right){
	while(right >= left){
		swap(arr[left++], arr[right--]);
	}
}
void full_permutation(int arr[], int len){
	qsort(arr, len, sizeof(int), cmp);
	println(arr, len);
	while(true){
		int j = len-1;
		int t = len;
		while(j >= 0 && arr[--j] >= arr[j+1]) ;
		if(j >= 0){
			while(arr[--t] <= arr[j]) ;
			swap(arr[t], arr[j]);
			reverse(arr, j+1, len-1);
			println(arr, len);
		}
		else{
			break;
		}
	}
}

int main(int argc, char* argv)
{
	int testArr[] = {23, 43, 8, 8};
	int len = sizeof(testArr)/sizeof(int);
	full_permutation(testArr, len);
	
	return 0;
}