DIV CSS 佈局教程網

JavaScript 全排列組合的遞迴實作思路
編輯:關於JavaScript     

給一組數字,把它們所有可能的排列順序都列出來——這是最典型的遞迴練習題。本文用一段不到二十行的 JavaScript 把這件事做完,並順帶談談為什麼遞迴在這裡特別合適。

先看成果:

程式碼

 <!DOCTYPE html> <html> <head> <title>demo</title> <script type="text/javascript"> var str = [1,2,3,4,5]; var count = 0; function arrange(s){ for(var i=0,length=str.length; i<length; i++) { if(s.length == length - 1) { if(s.indexOf(str[i]) < 0) { count++; console.log("組合"+count+"="+s + str[i]); } continue; } if(s.indexOf(str[i]) < 0) { arrange(s+str[i]); } } } arrange(""); </script> </head> <body> </body> </html> 

運作原理拆解

整個函式只有一個參數 s,代表「目前已經排好的前綴字串」。一開始傳入空字串,然後在每一層都做一次同樣的動作:把陣列從頭掃一遍,逐一嘗試接在後面。

去重是關鍵。 用 s.indexOf(str[i]) < 0 判斷這個數字是否已經出現在前綴裡,出現過就跳過。少了這一步,跑出來的就不只是排列,還會夾雜大量重複的組合。

終止條件藏在迴圈裡。 當 s.length == length - 1,代表再補一個數字就湊滿了整組,此時直接輸出結果並 continue,不必再往下遞迴。這樣寫比另外拉一個 if 判斷更省一層呼叫。

本質上是深度優先搜索。 你可以把這個過程想成一棵樹:每一層代表「第幾個位置要填什麼數字」,未被使用的數字就是分支,走到深度等於陣列長度時就是一片葉子,而所有葉子的集合就是答案。5 個數字會得到 120 種排列,時間複雜度 O(n!)。

想再往下鑽的話,可以試著改成「後續交換法」(在陣列上原地 swap,避免字串拼接產生的額外記憶體配置),或反過來用「字典序下一個排列」的迭代寫法。更多 JavaScript 算法主題可參考本站《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》與《JavaScript數據結構與算法技巧總結》。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved