Fonction de tri?

Question

J'ai besoin d'organiser un tableau de chaînes de longueur aléatoire dans le plus petit nombre de nouvelles chaînes avec une taille maximale. Y at-il une fonction ou quelque chose en javascript, ou quelque chose qui peut être traduit en javascript, qui va le faire? Par exemple, les nouvelles chaînes peuvent avoir une longueur maximale de 1000 caractères. Le tableau peut avoir des chaînes de longueurs 100, 48, 29, etc. Je voudrais combiner ces chaînes en autant de nouvelles chaînes que possible.

edit: Désolé si cela n'a pas de sens, j'ai fait de mon mieux.

Answer 1

Pour mon propre divertissement, j'ai écrit un simple algorithme d'emballage de poubelle. J'ai choisi un algorithme simple qui consiste à trier les chaînes d'entrée par longueur. Créez un nouveau bin. Mettez le premier (le plus long restant) chaîne dans la poubelle, puis continuez à le remplir avec les plus longues ficelles qui s'adapteront jusqu'à ce que plus de cordes s'adaptera. Créez une nouvelle corbeille, répétez. Pour le tester, j'alloue un tableau de chaînes de longueurs aléatoires et l'utilise comme entrée. Vous pouvez voir la sortie visuellement ici: http://jsfiddle.net/jfriend00/FqPKe/.

En l'exécutant plusieurs fois, il obtient un pourcentage de remplissage compris entre 91 et 98%, généralement autour de 96%. Évidemment, le pourcentage de remplissage est plus élevé s'il y a plus de chaînes courtes à remplir.

Voici le code:

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

Aucune méthode standard en Javascript, mais beaucoup de travail théorique a été fait sur ceci (c'est-à-dire le problème d'empaquetage de casier).

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

Certains exemples de code pseudo dans le lien - devrait être trivial pour traduire en javascript.

L'algorithme présenté ne sera pas optimal dans tous les cas. Pour trouver la solution optimale à votre exemple, vous aurez juste besoin de parcourir toutes les possibilités qui pourraient ne pas être si mauvaises en fonction du nombre de chaînes que vous avez.