演算法練習題-使用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>

執行結果:

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

歡迎推文分享:
Published 17 March 2012 08:01 AM 由 Jeffrey
Filed under: ,
Views: 22,533



意見
# 阿青 said on 17 March, 2012 09:01 AM

遞迴真的只應天上有~

實在很難用想像的來想出遞迴出現的程式結果

# Ammon said on 23 March, 2012 02:35 AM

//既然用了 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('')

);

# Jeffrey said on 23 March, 2012 10:27 AM

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

# dearplato said on 09 April, 2012 06:30 AM

在各位大師的基礎上再進一步改良：

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

# Edward said on 20 September, 2012 12:47 AM

黑大您好：

另外有一個問題想請教，

如果有一個陣列(長度不一定){"A","B","C"....}

請問如何用遞迴方法，列舉出所有的組合，如下：

A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA,

AAB, AAC, ABA, .......

語言可以是c#、java、vb都可以

謝謝您

# Jeffrey said on 22 September, 2012 11:13 AM

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

# Edward said on 23 September, 2012 09:10 PM

黑大您好：

我的想法是，陣列內容長度沒有限制。

希望可以把陣列的集合列出來，但是不同的順序是不同集合。

也就是說：

陣列一 = {"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.....

大至上是如此。

我想到用迴圈，就要寫死，沒辦法動態，所以才會想請教黑大是不是可以用遞迴來完成。

謝謝您

# Jeffrey said on 24 September, 2012 02:09 AM

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/

# Edward said on 24 September, 2012 10:19 PM

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

你的看法呢?

(必要的) 
(必要的) 
(選擇性的)
(必要的) 
(提醒: 因快取機制，您的留言幾分鐘後才會顯示在網站，請耐心稍候)

5 + 3 =

搜尋

Go

<March 2012>
SunMonTueWedThuFriSat
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567
 
RSS
創用 CC 授權條款
【廣告】
twMVC
最新回應

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人，十年的IT職場生涯，寫過系統、管過專案， 也帶過團隊，最後還是無怨無悔地選擇了技術鑽研這條路，近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

這個部落格


Syndication