Javascript: How to join an array the most efficiently into chunks less than 64 characters?

Question

I have a very long array of names like this:

namelist = [ "Andrew Alexander Brown", "Charlie Christopher Drake", "Edward Elsevier Furlong", "Gareth Gates Harper", "Indiana Chewbacca Jones", "Kevin M Lamarr", "Michael Randy Newman", "Oliver Terry Pratchett", "Queen Liz Regina", "Stuart Townsend", "Umar Vespa", "Woodford X Xanadu", "Yanick Zebra" ];

I would like to extract the names from the list into strings with each name separated by a pipe character (|). Each new string should be smaller than 48 characters, for instance the output should be like this (but less than or equal to 48 characters):

Andrew Alexander Brown|Charlie Christopher Drake|Edward Elsevier Furlong
Gareth Gates Harper|Indiana Chewbacca Jones|Kevin M Lamarr
Michael Randy Newman|Oliver Terry Pratchett|Queen Liz Regina
Stuart Townsend|Umar Vespa|Woodford X Xanadu|Yanick Zebra

I would like the number of new strings to be as small as possible, probably without maintaining the order of the strings in the array - but I am at a loss at how to do this in javascript.

I know I could do something like loop through the namelist and add the next name onto a temporary string. Check the length of this temporary string and output it if it exceeds 48 characters. Keep going around the loop until we have run out of names but this doesn't seem very efficient. For instance if a short name is followed by an extremely long name then characters (which could be filled by another smaller name in the temporary string) will be wasted.

Any pointers at how best to achieve this?

Answer 1

This is what is knows as The Bin Packing Problem

Solutions will depend on your definition of efficient, more efficient bin packing tends to take longer to compute. But less efficient bin packing tends to take much less computational resources (could be deemed more efficient in terms of computational resources).

Here is my solution using ECMA5 specifications, it sacrifices computational resources in favour of more efficient bin packing.

I have chosen to leave the powerSet function a general purpose one, that means it can be reused for other purposes. As @Bergi has highlighted, you may get better efficiency with respect to computational resources if you created a custom function which incorporates the first filter from joinStringsMaxCharacters

Javascript

General Power Set function

function powerSet(array) {
    var lastElement,
        sets;

    if (!array.length) {
        sets = [[]];
    } else {
        lastElement = array.pop();
        sets = powerSet(array).reduce(function (previous, element) {
            previous.push(element);
            element = element.slice();
            element.push(lastElement);
            previous.push(element);

            return previous;
        }, []);
    }

    return sets;
}

Helper functions

function isString(element) {
    return typeof element === 'string';
}

function isNotUsed(element) {
    return this.every(function (u) {
        return u.indexOf(element) === -1;
    });
}

function sumLength(s, el) {
    return s + el.length;
}

Packing bins with joined strings

function joinStringsMaxCharacters(arrayOfStrings, numberOfCharacters, separator) {
    if (!Array.isArray(arrayOfStrings) || !arrayOfStrings.every(isString)) {
        throw new TypeError('arrayOfStrings is not an array of strings!');
    }

    numberOfCharacters = numberOfCharacters >>> 0;
    if (!separator || !isString(separator)) {
        separator = '|';
    }

    var arrayLength = arrayOfStrings.length;

    return powerSet(arrayOfStrings).filter(function (set) {
        return set.length && (set.length === 1 || set.reduce(sumLength, set.length - 1) <= numberOfCharacters);
    }).sort(function (a, b) {
        return b.reduce(sumLength, b.length) - a.reduce(sumLength, a.length) || b.length - a.length;
    }).reduce(function (used, cur) {
        if (used.reduce(sumLength, 0) < arrayLength && cur.every(isNotUsed, used)) {
            used.push(cur);
        }

        return used;
    }, []).map(function (bin) {
        return bin.join(separator);
    });
}

Array of strings to be packed into bins

var nameList = [
    "Andrew Alexander Brown",
    "Charlie Christopher Drake",
    "Edward Elsevier Furlong",
    "Gareth Gates Harper",
    "Indiana Chewbacca Jones",
    "Kevin M Lamarr",
    "Michael Randy Newman",
    "Oliver Terry Pratchett",
    "Queen Liz Regina",
    "Stuart Townsend",
    "Umar Vespa",
    "Woodford X Xanadu",
    "Yanick Zebra"];

Pack the bins and display the content of each bin

joinStringsMaxCharacters(nameList, 48).forEach(function (bin) {
    console.log(bin);
});

Output

    Kevin M Lamarr|Stuart Townsend|Woodford X Xanadu
    Michael Randy Newman|Queen Liz Regina|Umar Vespa
    Charlie Christopher Drake|Oliver Terry Pratchett
    Edward Elsevier Furlong|Indiana Chewbacca Jones
    Andrew Alexander Brown|Gareth Gates Harper
    Yanick Zebra

On jsFiddle

Answer 2

var namelist= ["Andrew Alexander Brown", "Charlie Christopher Drake", "Edward Elsevier Furlong", "Gareth Gates Harper", "Indiana Chewbacca Jones", "Kevin M Lamarr", "Michael Randy Newman", "Oliver Terry Pratchett", "Queen Liz Regina", "Stuart Townsend", "Umar Vespa", "Woodford X Xanadu", "Yanick Zebra"];

var c48= [], next, temp= '', i= 0, L= namelist.length;
while(i<L){
    next= namelist[i++];
    if((temp+next).length<= 47) temp=temp? temp+'|'+next: next;
    else{
        c48.push(temp);
        temp= next;
    }
}

if(next)c48.push(next);
c48.join('\n')

/*  returned value: (String)
Andrew Alexander Brown|Charlie Christopher Drake
Edward Elsevier Furlong|Gareth Gates Harper
Indiana Chewbacca Jones|Kevin M Lamarr
Michael Randy Newman|Oliver Terry Pratchett
Queen Liz Regina|Stuart Townsend|Umar Vespa
Yanick Zebra
*/