13

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

 3 years ago
source link: https://blog.darkthread.net/blog/recursion-game/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
演算法練習題-使用JavaScript列舉所有排列組合-黑暗執行緒

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

執行結果:

1480-9839-o.gif

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

1481-f9d8-o.gif

and has 12 comments

Comments

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

# 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) } } }

Post a comment

Comment
Name Captcha 3 - 1 =

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK