演算法練習題-使用JavaScript列舉所有排列組合
14 |
跟朋友聊到一個有趣題目: 在產品資訊網頁上,依商品特性可能有多種屬性選項,例如: 尺寸、顏色、材質、版型... 等等,屬性的個數不固定,每個屬性的選項數目也不固定,目標是使用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
黑大,您果然有達到神人的等級,謝謝
# 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 .. 感謝
# 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) } } }
# by Vincent
to Jeffrey , 您太謙虛了,遞迴程式碼看起來既簡單又複雜,能夠寫遞迴程式果然是功力深厚,哈哈 沒想到2012 年的貼文,還會在短時間內得到回應,實在萬分感激
# by Omega
加到第四個維度時,算出來的答案,最後兩個維度會亂掉,也就是有時候是["XL", "L", "M", "S"]先,有時候是["純綿", "排汗"])先,不知這是要改哪裡才會讓順序正確呢? 遞迴真D難啊...
# by Jeffrey
to Omega, 能否在 jsbin 或 jsfiddle 提供可重現問題的範例?