Функция сортировки?

Question

Мне нужно организовать массив строк произвольной длины в наименьшее количество новых строк с максимальным размером. Есть ли функция или что-то в javascript, или что-то, что может быть переведено в javascript, которое сделает это?

Например, новые строки могут иметь максимальную длину 1000 символов. Массив может содержать строки длиной 100, 48, 29 и т. Д. Я хотел бы объединить эти строки в как можно меньшее количество новых строк.

edit: Извините, если это не имеет смысла, я старался изо всех сил.

Answer 1

Нет стандартного метода в Javascript, но была проделана большая теоретическая работа по этому вопросу (т. Е. Проблема с упаковкой в ​​бункер).должно быть тривиально, чтобы перевести на javascript.

Показанный алгоритм не будет оптимальным в каждом случае.Чтобы найти оптимальное решение для вашего примера, вам просто нужно перебрать каждую возможность, которая может быть не такой уж плохой, в зависимости от того, сколько у вас строк.

Answer 2

Для собственного развлечения я написал простой алгоритм упаковки бинов. Я выбрал простой алгоритм, который сортирует входные строки по длине. Создать новую корзину. Поместите первую (самую длинную оставшуюся) строку в мусорное ведро и затем продолжайте заполнять ее самыми длинными строками, которые будут соответствовать, пока больше не будет соответствовать строкам. Создайте новую корзину, повторите. Чтобы проверить это, я выделяю массив строк произвольной длины и использую его в качестве входных данных. Вы можете увидеть результат визуально здесь: 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>"

);