排序功能？

Question

我需要將一個隨機長度的字符串數組組織成最小數量的具有最大大小的新字符串。有沒有一個函數或什麼在JavaScript中，或者可以轉換爲JavaScript的東西，這將做到這一點？

例如，新字符串的最大長度可能爲1000個字符。數組可能有長度爲100,48,29等的字符串。我想將這些字符串組合成儘可能少的新字符串。

編輯：對不起，如果這沒有意義，我盡我所能。

Answer 1

對於我自己的娛樂，我寫了一個簡單的bin包裝算法。我選擇了一個簡單的算法，即按輸入字符串的長度排序。創建一個新的bin。將第一個（最長的剩餘）字符串放入容器中，然後用最長的字符串填充，直到不再有字符串適合爲止。創建一個新的垃圾箱，重複。爲了測試它，我分配了一串隨機長度的字符串，並將其用作輸入。你可以在這裏看到輸出：http://jsfiddle.net/jfriend00/FqPKe/。

運行它一堆，它會得到91-98％，通常約96％的填充百分比。顯然，如果有更多的短字符串填充，填充百分比會更高。

下面的代碼：

function generateRandomLengthStringArrays(num, maxLen) { 
    var sourceChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY1234567890"; 
    var sourceIndex = 0; 
    var result = []; 
    var len, temp, fill; 

    function getNextSourceChar() { 
     var ch = sourceChars.charAt(sourceIndex++); 
     if (sourceIndex >= sourceChars.length) { 
      sourceIndex = 0; 
     } 
     return(ch); 
    } 

    for (var i = 0; i < num; i++) { 
     len = Math.floor(Math.random() * maxLen); 
     temp = new String(); 
     fill = getNextSourceChar(); 
     // create string 
     for (var j = 0; j < len; j++) { 
      temp += fill; 
     } 
     result.push(temp); 
    } 
    return(result); 
} 

function packIntoFewestBins(input, maxLen) { 
    // we assume that none of the strings in input are longer than maxLen (they wouldn't fit in any bin) 

    var result = []; 
    // algorithm here is to put the longest string into a bin and 
    // then find the next longest one that will fit into that bin with it 
    // repeat until nothing more fits in the bin, put next longest into a new bin 
    // rinse, lather, repeat 

    var bin, i, tryAgain, binLen; 
    // sort the input strings by length (longest first) 
    input.sort(function(a, b) {return(b.length - a.length)}); 
    while (input.length > 0) { 
     bin = new String();      // create new bin 
     bin += input.shift();     // put first one in (longest we have left) and remove it 
     tryAgain = true; 
     while (bin.length < maxLen && tryAgain) { 
      tryAgain = false;     // if we don't find any more that fit, we'll stop after this iteration 
      binLen = bin.length;     // save locally for speed/convenience 
      // find longest string left that will fit in the bin 
      for (i = 0; i < input.length; i++) { 
       if (input[i].length + binLen <= maxLen) { 
        bin += input[i]; 
        input.splice(i, 1);   // remove this item from the array 
        tryAgain = true;    // try one more time 
        break;       // break out of for loop 
       } 
      } 
     } 
     result.push(bin); 
    } 
    return(result); 
} 

var binLength = 60; 
var numStrings = 100; 
var list = generateRandomLengthStringArrays(numStrings, binLength); 
var result = packIntoFewestBins(list, binLength); 
var capacity = result.length * binLength; 
var fillage = 0; 
for (var i = 0; i < result.length; i++) { 
    fillage += result[i].length; 
    $("#result").append(result[i] + "<br>") 
} 


$("#summary").html(
    "Fill percentage: " + ((fillage/capacity) * 100).toFixed(1) + "%<br>" + 
    "Number of Input Strings: " + numStrings + "<br>" + 
    "Number of Output Bins: " + result.length + "<br>" + 
    "Bin Legnth: " + binLength + "<br>" 

); 

Answer 2

Javascript中沒有標準方法，但在這方面已經做了大量的理論工作（即bin裝箱問題）。

http://en.wikipedia.org/wiki/Bin_packing_problem

的鏈接某些樣本僞碼 - 應該是微不足道翻譯爲JavaScript。

顯示的算法在每種情況下都不是最佳的。爲了找到你的例子的最佳解決方案，你只需要遍歷每一個可能不會那麼糟糕的可能性，這取決於你有多少個字符串。