演算法練習題-使用JavaScript列舉所有排列組合

2012-03-17 08:01 AM

跟朋友聊到一個有趣題目: 在產品資訊網頁上，依商品特性可能有多種屬性選項，例如: 尺寸、顏色、材質、版型... 等等，屬性的個數不固定，每個屬性的選項數目也不固定，目標是使用Javascript列舉出所有可能的組合。例如: 尺寸有L/M/S三種、顏色有黑/白兩種，就需列出黑L、黑M、黑S、白L、白M、白S共2*3=6種；若再加上長袖/短袖屬性，就要組出2*3*2共12種，以此類推。

遇到這種演算法小挑戰，程式魔人就像鯊魚嗅到血腥味般，立即興奮了起來，迫不及待想捲袖子動手玩一下。(程式魔人型的朋友可以在此打住先不要往下讀，自已先動手試試)

警告: 以下有雷!!(對程式魔人而言啦~)，後面涉及劇情演算法討論，可能會破壞Coding樂趣，請自行斟酌閱讀。

雖然俗話說"遞迴只應天上有，凡人應當用迴圈"，但這個例子十分適合用遞迴解決的典型，所以向天借膽，就搬出遞迴吧!! 補充說明都寫在註解裡，直接看程式:

<!DOCTYPE html>

<html>

<head>

    <title>OutterJoin</title>

    <script type='text/javascript'

            src='http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.7.1.js'></script>

    <script>

        $(function () {

            //排列組合用的維度

            var dimensions = [];

            dimensions.push(["紅", "綠", "藍"]);

            dimensions.push(["男", "女"]);

            dimensions.push(["XL", "L", "M", "S"]);

            //dimensions.push(["純綿", "排汗"]);

            //用以存放結果的陣列

            var results = [];

            //使用遞迴方式排列出所有組合

            //共有兩個傳入參數，目前處理的維度、排列組合時已累積的字首

            function explore(curDim, prefix) {

                //取出下一層維度

                var nextDim = dimensions.shift();

                for (var i = 0; i < curDim.length; i++) {

                    if (nextDim)

                        //若仍有下一層維度，繼續展開

                        //並將傳入字首加上目前維度選項成為下一層的字首

                        explore(nextDim, prefix + curDim[i] + "/");

                    else

                        //若已無下一層，則傳入字首加上目前維度選項成為結果

                        results.push(prefix + curDim[i]);

                //將下層維度存回，供上層維度其他選項使用

                if (nextDim) dimensions.push(nextDim);

            //傳入第一層維度開始演算

            explore(dimensions.shift(), "");

            //列出結果

            var html = [];

            $.each(results, function (idx, val) {

                html.push("<span>" + val + "</span>");

});

            $("#disp").html(html.join(""));

});

    </script>

    <style>

        body,input { font-size: 9pt; }

        #disp { width: 400px; }

        #disp span

            float: left; display: inline-block; padding: 4px;

            border: 1px solid gray; margin: 2px;

    </style>

</head>

<body>

    <div id="disp">

    </div>

</body>

</html>

執行結果:

再多一個維度也不是問題!

Comments

# 2012-03-17 09:01 AM by 阿青

遞迴真的只應天上有~ 實在很難用想像的來想出遞迴出現的程式結果

# 2012-03-23 02:35 AM by Ammon

//既然用了 jQuery 當然要多加利用 :> //善用 map 方法 function explore(arr, idx, prefix, undef) { var f = arr[idx++]; return f==undef?prefix : $.map(f, function(v){ return explore(arr, idx,prefix+'/'+v); }); } var result = explore(dimensions,0,''); //組字串也很好用 $("#disp").html( $.map(result,function(v) { return "" + v.substr(1) + "<br/>"; }).join('') );

# 2012-03-23 10:27 AM by Jeffrey

to Ammon, 爐火純青，嘆為觀止!! (一拜) 感謝補充

# 2012-04-09 06:30 AM by dearplato

在各位大師的基礎上再進一步改良： Array.prototype.crossJoin = function(idx, prefix, splitter, suffix, top) { var ary = this; var _suffix = ""; if(typeof(idx)!==typeof(0)){ idx = 0; } if(idx < 0){ idx = 0; } if(typeof(prefix)!==typeof("")){ prefix = ""; } if(typeof(splitter)!==typeof("")){ splitter = "/"; } if(typeof(suffix)!==typeof("")){ suffix = ""; } if(typeof(top)===typeof(undefined)){ if(idx >= ary.length-1){ idx = ary.length-1; } } var _item = ary[idx++]; if(top != undefined && idx != ary.length+1){ prefix = prefix + splitter; } if(idx == ary.length){ _suffix = suffix; } return _item == undefined ? prefix : _item.map(function(item){ return Array.prototype.crossJoin.call(ary, idx, prefix + item + _suffix, splitter, suffix, false); }); }; var dims = []; dims.push(["紅", "藍", "白"]); dims.push(["男", "女"]); dims.push(["XL", "L", "M", "S"]); dims.push(["純綿", "亞麻", "排汗"]); var result = dims.crossJoin(0,"[","/","]"); result.join();

# 2012-09-20 12:47 AM by Edward

黑大您好：另外有一個問題想請教，如果有一個陣列(長度不一定){"A","B","C"....} 請問如何用遞迴方法，列舉出所有的組合，如下： A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA, AAB, AAC, ABA, ....... 語言可以是c#、java、vb都可以謝謝您

# 2012-09-22 11:13 AM by Jeffrey

to Edward, 你舉的例子中，字母可以出現一次以上，似乎有點像列舉三進位數字的感覺，似乎用迴圈比遞迴更合適。另外，舉例中最多為三碼，是因為有"A", "B", "C"三個元素的緣故? 還是另外指定？

# 2012-09-23 09:10 PM by Edward

黑大您好：我的想法是，陣列內容長度沒有限制。希望可以把陣列的集合列出來，但是不同的順序是不同集合。也就是說：陣列一 = {"1"，"b"} 列出：1,b,11,1b,bb,b1 陣列二 = {"a","C","3"} 列出：a,C,3,aa,aC,a3,Ca,CC,C3,3a,3C,33,aaa,aaC,aa3, aCa,aCC,aC3..... 大至上是如此。我想到用迴圈，就要寫死，沒辦法動態，所以才會想請教黑大是不是可以用遞迴來完成。謝謝您

# 2012-09-24 02:09 AM by Jeffrey

to Edward, 我用JavaScript簡單試寫如下: alert(JSON.stringify(enumerateAll([ "1", "b" ]))); alert(JSON.stringify(enumerateAll([ "a", "C", "3" ]))); alert(JSON.stringify(enumerateAll([ "a", "b", "c", "d" ]))); function enumerateAll(digits) { var res = []; explore("", digits, 1); return res; function explore(prefix, digits, level) { for (var i = 0; i < digits.length; i++) { res.push(prefix + digits[i]); } if (level < digits.length) { for (var i = 0; i < digits.length; i++) { explore(prefix + digits[i], digits, level + 1); } } } } 線上展示: http://jsfiddle.net/sSaR6/

# 2012-09-24 10:19 PM by Edward

黑大，您果然有達到神人的等級，謝謝

# 2021-02-18 06:42 PM by vincent

to jeffrey 請問一下大神如何列出不重複的排列組合陣列一 = {"1"，"b"} 列出：1,b,1b,b1, 陣列二 = {"a","C","3"} 列出：a,C,3,,aC,a3,Ca,C3,3a,3C,aC3,a3C,Ca3,C3a,3aC,3Ca .. 感謝

# 2021-02-20 12:43 PM by Jeffrey

to vincent, 離大神還很遠，老司機試改了一個版本，看看有無符合規格 http://jsfiddle.net/darkthread/nv34fhrq/ function enumerateAll(digits) { var res = []; explore("", digits); return res; function explore(prefix, digits) { for (var i = 0; i < digits.length; i++) { res.push(prefix + digits[i]); var remainDigits = digits.slice(); remainDigits.splice(i, 1); explore(prefix + digits[i], remainDigits) } } }

# 2021-02-21 12:10 PM by Vincent

to Jeffrey , 您太謙虛了，遞迴程式碼看起來既簡單又複雜，能夠寫遞迴程式果然是功力深厚，哈哈沒想到2012 年的貼文，還會在短時間內得到回應，實在萬分感激

# 2022-01-26 01:51 AM by Omega

加到第四個維度時，算出來的答案，最後兩個維度會亂掉，也就是有時候是["XL", "L", "M", "S"]先，有時候是["純綿", "排汗"])先，不知這是要改哪裡才會讓順序正確呢？遞迴真D難啊...

# 2022-01-27 08:27 PM by Jeffrey

to Omega, 能否在 jsbin 或 jsfiddle 提供可重現問題的範例？