ソート機能？

Question

ランダムな長さの文字列を、最小の数の新しい文字列に最大サイズで整理する必要があります。関数や何かがjavascriptであるか、javascriptに変換できるものがありますか？

たとえば、新しい文字列の最大長は1000文字です。配列は長さが100、48、29などの文字列を持つかもしれません。これらの文字列を可能な限り新しい文字列に結合したいと思います。

編集：申し訳ありませんが、これは意味がない場合は、私はベストを尽くしました。

Answer 1

私自身の娯楽のために、私は単純なビンパッキングアルゴリズムを書いた。私は入力文字列を長さでソートする単純なアルゴリズムを選んだ。新しいビンを作成します。最初の（最長の残りの）文字列をビンに入れ、それ以上の文字列が収まらなくなるまで収まるような最長の文字列で続けてください。新しいビンを作成し、繰り返します。それをテストするために、私はランダムな長さの文字列の配列を割り当て、それを入力として使用します。視覚的に出力を見ることができます：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での標準的な方法はありませんが、理論的な作業がこれで実行されています（つまり、ビンのパッキングの問題）。

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

リンクのいくつかのサンプル擬似コード - JavaScriptに変換するのは簡単でなければなりません。

示されているアルゴリズムはすべての場合に最適ではありません。あなたの例に最適な解を見つけるには、あなたが持っている文字列の数に応じてそれほど悪くない可能性のあるすべての可能性を繰り返し処理するだけです。