Permutation(排列組合)

排列問(wèn)題:

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

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

當(dāng)n=1時(shí)，Permutation(R)={r},r是集合R中唯一的元素；

當(dāng)n>1時(shí)，Permutation(R)由(r1)Permutation(R1),(r2)Permutation(R2),?...,?(rn)Permutation(Rn)構(gòu)成。

依次遞歸定義,則可設(shè)計(jì)產(chǎn)生Permutation(X)的遞歸算法如下:

template <typename Type> void permutation(Type *array, int front, int last) {//已經(jīng)遞歸到了最后一個(gè)元素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){// 不斷的從下標(biāo)為[front ~ last]的元素中選擇一個(gè)元素//作為當(dāng)前序列的開(kāi)頭元素std::swap(array[front], array[i]);permutation(array, front+1, last);std::swap(array[front], array[i]);}} }

算法說(shuō)明:

算法Permutation(array,?k,?m)遞歸地產(chǎn)生所有前綴是array[0:k-1],且后綴是array[k:m]的全排列的所有排列.函數(shù)調(diào)用(list,?0,?n-1)則產(chǎn)生list[0:n-1]的全排列.

?

算法演示:

char?str[]?=?“abc”;的遞歸調(diào)用過(guò)程如圖:

小結(jié):

雖然我們自己實(shí)現(xiàn)了Permutation,?但C++?STL中也實(shí)現(xiàn)了std::next_permutation算法,?在一般應(yīng)用中,?我比較推薦使用STL中已經(jīng)實(shí)現(xiàn)好的next_permutation,?畢竟STL的代碼質(zhì)量還是非常高的,?而且速度一點(diǎn)也不遜色于我們的實(shí)現(xiàn);

?

插入排序

插入排序是低級(jí)排序中速度最快的一種(冒泡/選擇/插入排序效率均為O(N^2)),但是跟快速排序(NlogN),歸并排序(NlogN)還是有一定的差距的⊙﹏⊙b汗!

算法思想:

不斷的從尚未排序的序列中選擇一個(gè)元素插入到已經(jīng)排好序的序列中(當(dāng)然,會(huì)有一個(gè)選擇插入位置的過(guò)程:選擇一個(gè)位置,?該位置前的元素都比該元素小,?該位置后的元素都比該元素大),類(lèi)似于現(xiàn)實(shí)生活中的斗地主的摸排過(guò)程.

//實(shí)現(xiàn)與解析 /**說(shuō)明:outer:第一個(gè)未排序的元素inner:搜索第一個(gè)小于tmp的元素的位置tmp: 用于暫存第一個(gè)尚未排序的元素 */ template <typename Type> void insertionSort(Type *begin, Type *end) throw (std::range_error) {if ((begin == end) || (begin == NULL) || (end == NULL))throw std::range_error("pointer unavailable");//假設(shè)第一個(gè)元素已經(jīng)排好序了for (Type *outer = begin+1; outer < end; ++outer){Type tmp = *outer; //暫存第一個(gè)未排序的元素Type *inner = outer;//inner 不斷尋找一個(gè)位置(*(inner-1) <= tmp),//使得tmp->*inner(tmp所保存的值插入到inner位置)while (inner > begin && *(inner-1) > tmp){*inner = *(inner-1); //元素后移-- inner; //指針前移}*inner = tmp; //將元素插入已排序序列} }template <typename Iter> void insertionSort(Iter begin, Iter end) {return insertionSort(&(*begin), &(*end)); } /**insertionSort_2算法的由來(lái):可以使用*begin(序列的第一個(gè)元素)作為哨兵,這樣就可以省去insertionSort 中第15行的inner > begin判斷,但付出的代價(jià)是begin所指向的位置不能再存儲(chǔ)有用的數(shù)據(jù),只能被用作排序的哨兵 -> 以空間換時(shí)間(個(gè)人感覺(jué)沒(méi)什么必要...) */ template <typename Type> void insertionSort_2(Type *begin, Type *end) throw (std::range_error) {if ((begin == end) || (begin == NULL) || (end == NULL))throw std::range_error("pointer unavailable");for (Type *outer = begin+2; outer < end; ++outer){*begin = *outer;Type *inner = outer;//因?yàn)?begin不可能 > *begin, 所以該循環(huán)一定會(huì)退出while (*(inner-1) > *begin){*(inner) = *(inner-1);--inner;}*inner = *begin;} }

附-permutation與std::next_permutation測(cè)試代碼

int main() {vector<char> str;for (char ch = 'a'; ch <= 'c'; ++ch)str.push_back(ch);permutation(&(*str.begin()), 0, 2);cout << "----------" << endl;typedef vector<char>::iterator Iter_type;do{for (Iter_type iter = str.begin(); iter != str.end(); ++iter)cout << *iter << ' ';cout << endl;}while (std::next_permutation(str.begin(), str.end()));return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构基础(3) --Permutation 插入排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。