您當前位置：首頁 > php開源 > php教程 > 數據結構基礎(3) --Permutation & 插入排序

數據結構基礎(3) --Permutation & 插入排序

來源：程序員人生發布時間：2015-01-04 09:02:52 閱讀次數：3454次

Permutation(排列組合)

排列問題:

設R = {r1, r2, ... , rn}是要進行排列的n個元素, Ri = R-{ri}; 集合X中元素的全排列記為Permutation(X), (ri)Permutation(X)表示在全排列Permutation(X)的每個排列前加上前綴ri得到的排列.

R的全排列可歸納定義以下:

當n=1時，Permutation(R)={r},r是集合R中唯1的元素；

當n>1時，Permutation(R)由(r1)Permutation(R1),(r2)Permutation(R2), ..., (rn)Permutation(Rn)構成。

順次遞歸定義,則可設計產生Permutation(X)的遞歸算法以下:

template <typename Type> void permutation(Type *array, int front, int last) { //已遞歸到了最后1個元素 if (front == last) { //打印輸出 for (int i = 0; i < front; ++i) { cout << array[i] << ' '; } cout << array[front] << endl; return ; } else { for (int i = front; i <= last; ++i) { // 不斷的從下標為[front ~ last]的元素當選擇1個元素 //作為當前序列的開頭元素 std::swap(array[front], array[i]); permutation(array, front+1, last); std::swap(array[front], array[i]); } } }

算法說明:

算法Permutation(array, k, m)遞歸地產生所有前綴是array[0:k⑴],且后綴是array[k:m]的全排列的所有排列.函數調用(list, 0, n⑴)則產生list[0:n⑴]的全排列.

算法演示:

char str[] = “abc”;的遞歸調用進程如圖: