Algorithm to balance variably-sized items into roughly-balanced sets

Question

I'm seeking an algorithm to split a list of items of varying sizes into "N" number of similarly-sized groups.

Specifically, I'm working on an ASP.NET site in C# where I have a (database-retrieved) list of strings. The strings are of varying lengths. I have a set of columns which need to display the strings. I need an algorithm that will find the most balanced sets (item order is irrelevant) to allow the final columns to be as balanced as possible.

Abstracted Example:

Creating 3 columns.

Items to distribute:

 - Item A - height 5
 - Item B - height 3
 - Item C - height 7
 - Item D - height 2
 - Item E - height 3

Desired output:

Column 1: Item A, Item D
Column 2: Item C
Column 3: Item B, Item E

Answer 1

The quickest thing to do is probably just insert each new item into the smallest list (where "smallest" is the sum of the sizes of all the items in the list).

Answer 2

This seems like a variant of the Packing Boxes (or Bin Packing) problem, which is where you try to fit a collection of variable sized items into as few containers as possible:

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

Depending on the size of your set of items, you could probably brute force a solution fairly simply, looking for the combination with the smallest difference between sizes. For larger sets this becomes quite a difficult problem, and you might be better with a "simple" algorithm that gets you somewhere close to a good answer.

Answer 3

Have a look at job shop scheduling algorithms where we have a number of jobs of varying sizes to be distrubted over machines so that the total production time is minimal.

Answer 4

Try something very very basic

        public static List<List<int>> Balance(List<int> input)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(input);

            values.Sort();

            var max = values.Max();
            var maxIndex = values.FindIndex(v => v == max);
            for (int i = maxIndex; i < values.Count; i++)
            {
                result.Add(new List<int> { max });
            }
            var limit = maxIndex;
            for (int i = 0; i < limit / 2; i++)
            {
                result.Add(new List<int> { values[i], values[(limit - 1) - i] });
            }
            if (limit % 2 != 0)
            {
                result.Add(new List<int> { values[limit / 2] });
            }
        }

        return result;
    }

This method can be used in case you need to group by two elements. You can change it to group elements till a predefined value is reached (e.g. 10). Probably I'll post the other version to.

Answer 5

Here's the other version which can create groups of desired length.

        public static List<List<int>> Balance(List<int> input, int desiredLimit)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(input);
            values.Sort();

            var start = 0;
            var end = values.Count - 1;
            var orderedValues = new List<int>(values.Count);
            while (start < end)
            {
                orderedValues.Add(values[start]);
                orderedValues.Add(values[end]);
                start++;
                end--;
            }
            if (values.Count % 2 != 0)
            {
                orderedValues.Add(values[values.Count / 2]);
            }

            var total = 0;
            var line = new List<int>();

            for (int i = 0; i < orderedValues.Count; i++)
            {
                var v = orderedValues[i];
                total += v;
                if (total <= desiredLimit)
                {
                    line.Add(v);
                }
                else
                {
                    total = v;
                    result.Add(line);
                    line = new List<int>() { v };
                }
            }
            result.Add(line);
        }

        return result;
    }