排列問題的遞歸算法

1、算法設(shè)計(jì)與分析 排列問題的遞歸算法14.1.4 排列問題的遞歸算法 有n個(gè)元素，把它們編號(hào)為1，2n，用一個(gè)數(shù)組A 來存放所生成的排列，然后輸出它們。假定開始時(shí)n個(gè)元素以依次存放在數(shù)組A中，為了生成這n個(gè)元素的所有排列，可以采取下面的步驟： （1）第一個(gè)元素為1，即排列的第一個(gè)元素為1，生成后面n-1個(gè)元素的排列。 1 2 3 4nn-1個(gè)元素排列 （2）第一個(gè)元素和第二個(gè)元素互換，使排列的第一個(gè)元素為2，生成后面n-1個(gè)元素的排列。 （3）如此繼續(xù)，最后第一個(gè)元素和第n個(gè)元素互換，使排列的第一個(gè)元素為n，生成后面n-1個(gè)元素的排列。 2 1 3 4n n 2 3 41n-1個(gè)元素排列n-1個(gè)

2、元素排列 在上面的第一步 ，為生成后面n-1個(gè)元素的排列，繼續(xù)采取下面的步驟： （1）第二個(gè)元素為2，即排列的第二個(gè)元素為2，生成后面n-2個(gè)元素的排列。 （2）第二個(gè)元素和第三個(gè)元素互換，使排列的第二個(gè)元素為3，生成后面n-2個(gè)元素的排列。 1 2 3 4nn-2個(gè)元素排列1 3 2 4nn-2個(gè)元素排列 （3）如此繼續(xù)，最后第二個(gè)元素和第n個(gè)元素互換，使排列的第二個(gè)元素為n，生成后面n-2個(gè)元素的排列。 這種步驟一直繼續(xù)，當(dāng)排列的前n-2個(gè)元素已確定后，為生成后面2個(gè)元素的排列，可以： （1）第n-1個(gè)元素為n-1,即排列的第n-1個(gè)元素為n-1，生成后面1個(gè)元素的排列,此時(shí)n個(gè)元素已構(gòu)成

3、一個(gè)排列。 （2）第n-1個(gè)元素和第n個(gè)元素互換，使排列的第n-1個(gè)元素為n，生成后面1個(gè)元素的排列,此時(shí)n個(gè)元素已構(gòu)成一個(gè)排列。 1 n 3 42n-2個(gè)元素排列 令排列算法perm(A,k,n)表示生成數(shù)組后面 個(gè)元素的排列。通過上面的分析有： （1）基礎(chǔ)步：k=1,只有一個(gè)元素，已構(gòu)成一個(gè)排列。 （2）歸納步：對(duì)任意的k,1k=n完成perm(A,k-1,n),逐一對(duì)第n-k元素與第n-kn元素進(jìn)行互換，每互換一次，就執(zhí)行一次perm(A,k -1,n)操作，產(chǎn)生一個(gè)排列。 由此，排列生成的遞歸算法可描述如下：算法4.5 排列的生成輸入：數(shù)組A ,數(shù)組的元素個(gè)數(shù)n 輸出：數(shù)組A 的所有排列 1.template 2.void perm(Type A,int k,int n)3.4.int i;5.if (k=1)6.for (i=0;in;i+) /* 已構(gòu)成一個(gè)排列,輸出它 */7.cout Ai;8.else9.10.for (i=n-k;in;i+) /* 生成后續(xù)的一系列排列 */11.12. swap(Ai,An-k);13.perm(A,k-1,n);14.swap(Ai,An-k);.1.5 遞歸算法的討論 結(jié)構(gòu)清晰明了、容易閱讀、容易用數(shù)學(xué)歸納法證明它的正確性。程序調(diào)試很方便。 遞歸深度加深，工作棧所需空間