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

I'm seeking an algorithm to split a list of items of varying sizes into "N" number of similarl开发者_JAVA百科y-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

---

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).

---

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.

---

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.

---

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;
    }

---

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.

---

If you have two columns, this sounds like an application of the Partition Problem. The problem is NP-complete, but there is a dynamic programming solution that is pseudo-polynomial time. http://en.wikipedia.org/wiki/Partition_problem

If you increase the number of columns beyond two, then there is no pseudo-polynomial time solution. http://en.wikipedia.org/wiki/3-partition_problem

---

Here is the generic code that implement the accepted answer:

• just insert each new item into the smallest list

• sort the items first (from big to small), that will improve a lot

    class Item { internal Item(int weight) { Weight = weight; } internal int Weight { get; } }
  
    [Test]
    public void Test1() {
  
       var A = new Item(5);
       var B = new Item(3);
       var C = new Item(7);
       var D = new Item(2);
       var E = new Item(3);
  
       Item[][] result = AlgoToBuildBalancedPartition.Go(new[] { A, B, C, D, E }, t => t.Weight, 3);
       Assert.AreEqual(result.Length, 3);
       Assert.Contains(C, result[0]);
       Assert.Contains(A, result[1]);
       Assert.Contains(D, result[1]);
       Assert.Contains(B, result[2]);
       Assert.Contains(E, result[2]);
    }
  
    //--------------------------------------------------
  
    public static class AlgoToBuildBalancedPartition {
  
       public static T[][] Go<T>(
              IEnumerable<T> seq,
              Func<T, int> getWeightProc,
              int maxNbPartitions) where T : class {
          Debug.Assert(!seq.IsNullOrEmpty());
          Debug.Assert(getWeightProc != null);
          Debug.Assert(maxNbPartitions >= 2);
  
          var partitions = new List<Partition<T>>(maxNbPartitions);
  
          T[] seqDescending = seq.OrderByDescending(getWeightProc).ToArray();
          int count = seqDescending.Length;
  
          for (var i = 0; i < count; i++) {
             T item = seqDescending[i];
             if (partitions.Count < maxNbPartitions) {
                partitions.Add(new Partition<T>(item, getWeightProc));
                continue;
             }
  
             // Get partition with smallest weight
             Debug.Assert(partitions.Count == maxNbPartitions);
             var partitionWithMinWeight = partitions[0];
             for (var j = 1; j < maxNbPartitions; j++) {
                var partition = partitions[j];
                if (partition.TotalWeight > partitionWithMinWeight.TotalWeight) { continue; }
                partitionWithMinWeight = partition;
             }
  
             partitionWithMinWeight.AddItem(item);
          }
  
          return partitions.Select(p => p.Items.ToArray()).ToArray();
       }
  
  
       private sealed class Partition<T> where T : class {
          internal Partition(T firstItem, Func<T, int> getWeightProc) {
             Debug.Assert(firstItem != null);
             Debug.Assert(getWeightProc != null);
             m_GetWeightProc = getWeightProc;
             AddItem(firstItem);
          }
          private readonly Func<T, int> m_GetWeightProc;
          internal List<T> Items { get; } = new List<T>();
          internal void AddItem(T item) {
             Debug.Assert(item != null);
             Items.Add(item);
             TotalWeight += m_GetWeightProc(item);
          }
          internal int TotalWeight { get; private set; } = 0;
       }
    }