全排列生成算法-資料下載頁(yè)
2025-08-04 14:16本頁(yè)面
【正文】 ext NextLoopEnd Sub全排列的生成方法用遞歸方式描述比較簡(jiǎn)潔，實(shí)現(xiàn)的方法也有多種。1）回溯法回溯法通常是構(gòu)造一顆生成樹(shù)。以3個(gè)元素為例；樹(shù)的節(jié)點(diǎn)有個(gè)數(shù)據(jù)，可取值是3。如果某個(gè)為0，則表示尚未取值。初始狀態(tài)是(0，0，0)，第1個(gè)元素值可以分別挑選1，2，3，因此擴(kuò)展出3個(gè)子結(jié)點(diǎn)。用相同方法找出這些結(jié)點(diǎn)的第2個(gè)元素的可能值，如此反復(fù)進(jìn)行，一旦出現(xiàn)新結(jié)點(diǎn)的3個(gè)數(shù)據(jù)全非零，那就找到了一種全排列方案。當(dāng)嘗試了所有可能方案，即獲得了問(wèn)題的解答。程序代碼如下：Private Sub Remo(p() As Integer, ByVal k As Integer) Dim b As Boolean If k = n + 1 Then 39。如果kn則輸出一個(gè)排列OutL p Else 39。否則For i = 1 To n b = False 39。重復(fù)元素標(biāo)志置為Falsep(k) = i 39。第k個(gè)元素設(shè)為iFor j = 1 To k 1 39。檢查是否存在重復(fù)元素 If i = p(j) Then 39。有重復(fù) b = True 39。設(shè)置重復(fù)標(biāo)志為T(mén)rue j = k 1 39?；厮軪nd IfNext 39。換一個(gè)元素試探If Not b Then Remo, k + 1 39。無(wú)重復(fù)，繼續(xù)遞歸找下一個(gè)元素 NextEnd IfEnd Sub2）遞歸算法如果用P表示n個(gè)元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個(gè)元素的排列可遞歸定義為：如果n=1，則排列P只有一個(gè)元素i如果n1，則排列P由排列(i)Pi構(gòu)成（i=....、n1）。根據(jù)定義，容易看出如果已經(jīng)生成了k1個(gè)元素的排列，那么，k個(gè)元素的排列可以在每個(gè)k1個(gè)元素的排列Pi前添加元素i而生成。例如2個(gè)元素的排列是 1 2和2 1，對(duì)與個(gè)元素而言，p1是2 3和3 2，在每個(gè)排列前加上1即生成1 2 3和1 3 2兩個(gè)新排列，p2和p3則是1 3 1和1 2 1，按同樣方法可生成新排列2 1 2 3 1和3 1 3 2 1。程序代碼如下：Private Sub Recu(p() As Integer, ByVal k As Integer) If k = n ThenOutL p ElseFor i = k To n Swap p(k), p(i) Recu p, k + 1 Swap p(k), p(i) Next End IfEnd Sub3）循環(huán)移位法如果已經(jīng)生成了k1個(gè)元素的排列，則在每個(gè)排列后添加元素k使之成為k個(gè)元素的排列，然后將每個(gè)排列循環(huán)左移（右移），每移動(dòng)一次就產(chǎn)生一個(gè)新的排列。例如2個(gè)元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環(huán)左移可再生成新排列2 3 3 1 2，同樣2 1 可生成新排列2 1 1 3 2和3 2 1。程序代碼如下：Private Sub Cycl(p() As Integer,ByVal k As Integer)If k n Then OutL p tot = tot + 1Else For i = 0 To k 1t = p(1)For j = 2 To kp(j 1) = p(j)Nextp(k) = tCycl p,k + 1 NextEnd IfEnd Sub
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1