全排列生成算法(參考版)
2025-08-07 14:16本頁面
【正文】 在1 2 后加上3成為新排列1 2 3，將它循環(huán)左移可再生成新排列2 3 3 1 2，同樣2 1 可生成新排列2 1 1 3 2和3 2 1。 End IfEnd Sub3）循環(huán)移位法如果已經生成了k1個元素的排列，則在每個排列后添加元素k使之成為k個元素的排列，然后將每個排列循環(huán)左移（右移），每移動一次就產生一個新的排列。 Swap p(k), p(i) Next Recu p, k + 1 Swap p(k), p(i) ElseFor i = k To n If k = n ThenOutL p程序代碼如下：Private Sub Recu(p() As Integer, ByVal k As Integer)根據(jù)定義，容易看出如果已經生成了k1個元素的排列，那么，k個元素的排列可以在每個k1個元素的排列Pi前添加元素i而生成。 39。 換一個元素試探If Not b Then Remo, k + 1 39。 j = k 1 設置重復標志為True 39。 39。 第k個元素設為iFor j = 1 To k 1 39。 b = False 否則For i = 1 To n 39。 If k = n + 1 Then Dim b As Boolean 程序代碼如下：Private Sub Remo(p() As Integer, ByVal k As Integer)用相同方法找出這些結點的第2個元素的可能值，如此反復進行，一旦出現(xiàn)新結點的3個數(shù)據(jù)全非零，那就找到了一種全排列方案。如果某個為0，則表示尚未取值。1）回溯法回溯法通常是構造一顆生成樹。檢查排列中的元素是否重復For j = i + 1 To nIf p(i) = p(j) Then GoTo Nextn 39。 For i = 1 To n 1 Next第一個元素值超過n，則所有排列都找到End If 39。 39。 39。 39。 39。 p(n) = p(n) + n 1 Do While n 0OutL pNextn: Dim i As Integer, j As Integer Private Sub Incr(p() As Integer, ByVal n As Integer) 3，從它開始，第3個元素是3，3+2=5，5 Mod 3=2，第2個元素是2，2+1=3，所以新排列是1 3 2。 2（n進制法）1）從原始排列p=p1p2......pn開始，第n位加n1，如果該位的值超過n，則將它除以n，用余數(shù)取代該位，并進位（將第n1位加1）2）再按同樣方法處理n1位，n2位，......，直至不再發(fā)生進位為止，處理完一個排列就產生了一個新的排列3）將其中有相同元素的排列去掉4）當?shù)谝粋€元素的值n則結束以3個數(shù)3的排列為例：原始排列是1 Swap p(1), p(2)NextEnd Sub Next移動一次產生一個新排列 39。 For j = 1 To n 1 OutL p Swap p(n), p(n 1) Next移動一次產生一個新排列 39。 For j = n To 2 Step 1 OutL p m = m * iNextFor i = 1 To m 1 計算(n1)!/2 程序代碼如下：Private Sub Adja(p() As Integer, ByVal n As Integer)m = 1For i = 3 To n 1 End If LoopEnd Sub鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的。將n與其左邊數(shù)字交換
環(huán)評公示相關推薦
鄂ICP備17016276號-1