排列問題的遞歸算法

排列問題的遞歸算法第1頁，共11頁，2023年，2月20日，星期一4.1.4排列問題的遞歸算法

有n個元素，把它們編號為1，2…n，用一個數(shù)組A來存放所生成的排列，然后輸出它們。假定開始時n個元素以依次存放在數(shù)組A中，為了生成這n個元素的所有排列，可以采取下面的步驟：（1）第一個元素為1，即排列的第一個元素為1，生成后面n-1個元素的排列。

第2頁，共11頁，2023年，2月20日，星期一

（2）第一個元素和第二個元素互換，使排列的第一個元素為2，生成后面n-1個元素的排列。

（3）如此繼續(xù)，最后第一個元素和第n個元素互換，使排列的第一個元素為n，生成后面n-1個元素的排列。第3頁，共11頁，2023年，2月20日，星期一

在上面的第一步，為生成后面n-1個元素的排列，繼續(xù)采取下面的步驟：（1）第二個元素為2，即排列的第二個元素為2，生成后面n-2個元素的排列。（2）第二個元素和第三個元素互換，使排列的第二個元素為3，生成后面n-2個元素的排列。

第4頁，共11頁，2023年，2月20日，星期一

（3）如此繼續(xù)，最后第二個元素和第n個元素互換，使排列的第二個元素為n，生成后面n-2個元素的排列。

這種步驟一直繼續(xù)，當排列的前n-2個元素已確定后，為生成后面2個元素的排列，可以：（1）第n-1個元素為n-1,即排列的第n-1個元素為n-1，生成后面1個元素的排列,此時n個元素已構(gòu)成一個排列。（2）第n-1個元素和第n個元素互換，使排列的第n-1個元素為n，生成后面1個元素的排列,此時n個元素已構(gòu)成一個排列。

第5頁，共11頁，2023年，2月20日，星期一

令排列算法perm(A,k,n)表示生成數(shù)組后面?zhèn)€元素的排列。通過上面的分析有：（1）基礎(chǔ)步：k=1,只有一個元素，已構(gòu)成一個排列。（2）歸納步：對任意的k,1<k<=n完成perm(A,k-1,n),逐一對第n-k元素與第n-k~n元素進行互換，每互換一次，就執(zhí)行一次perm(A,k-1,n)操作，產(chǎn)生一個排列。

由此，排列生成的遞歸算法可描述如下：第6頁，共11頁，2023年，2月20日，星期一算法4.5排列的生成輸入：數(shù)組A[],數(shù)組的元素個數(shù)n輸出：數(shù)組A[]的所有排列1.template<classType>2.voidperm(TypeA[],intk,intn)3.{4. inti;5. if(k==1)6. for(i=0;i<n;i++) /*已構(gòu)成一個排列,輸出它*/7. cout<<A[i];8. else9. {10. for(i=n-k;i<n;i++)/*生成后續(xù)的一系列排列*/11. {12. swap(A[i],A[n-k]);13. perm(A,k-1,n);14. swap(A[i],A[n-k]);15. }16. }17.}第7頁，共11頁，2023年，2月20日，星期一第8頁，共11頁，2023年，2月20日，星期一第9頁，共11頁，2023年，2月20日，星期一4.1.5遞歸算法的討論

結(jié)構(gòu)清晰明了、容易閱讀、容易用數(shù)學(xué)歸納法證明它的正確性。程序調(diào)試很方便。遞歸深度加深，工作棧所需空間增大，遞歸調(diào)用時所花輔助操作增多。運行效率較低?？?/p>