跟朋友聊到一個有趣題目: 在產品資訊網頁上,依商品特性可能有多種屬性選項,例如: 尺寸、顏色、材質、版型... 等等,屬性的個數不固定,每個屬性的選項數目也不固定,目標是使用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

# by 阿青

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

# 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('') );

# by Jeffrey

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

# 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();

# by Edward

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

# by Jeffrey

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

# 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..... 大至上是如此。 我想到用迴圈,就要寫死,沒辦法動態,所以才會想請教黑大是不是可以用遞迴來完成。 謝謝您

# 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/

# by Edward

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

Post a comment


71 - 6 =