How to Group a List of Objects by a Running Total?

Question

Lets say I have an object that looks like this

public class TestItem
{
    public Int32 ID { get; set; }
    public Int32 Weight { get; set; }
}

I have a list of these objects, and I want to split the list when the running total of the sum of Weight exceeds a limit, say 100.

I tried doing this in Linq, and I couldnt quite get the right grouping. Then I tried to do this using foreach iterations, and got groups that exceeded the limit. I've looked at some Rollup linq Extensions, and tried a few different strategies go check the limits and I still got groups that were higher than the limit.

Even allowing for when the a single TestItem already exceeds the limit, by my application that is fine.

I'm out of ideas on how to create groups based on a set limit on a running total. Any ideas?

Edit #1 this is what I just tried. Still no dice.

double sum = 0;
int cartonnum = 1;
var groupedCarton = ordered.GroupBy(x =>
{
    sum += x.TotalWeight * x.Qty;
    if (sum > maxWeight)
    {
         sum = 0;
         cartonnum++;
         return cartonnum;
    }else{

        return cartonnum;
    }
});

foreach (var g in groupedCarton)
{
    foreach (var item in g)
    {
        item.CartonNumber = g.Key;
    }
}

var uniqueLine = ordered.GroupBy(g => g.CartonNumber, (key, g) => new { Carton = key, Sum = g.Sum(k => k.TotalWeight) }).ToList();

Answer 1

With the latest edit you are getting closer to a solution and you have clarified your question. Although it is possible solving this using some LINQ groupings, it does not really clarify the rules you are trying to implement, nor make the "shape" of your expected output explicit. Doing so would make it easier to reason about.

I would suggest doing something like below:

namespace TryOuts
{
    using System;
    using System.Linq;
    using System.Collections.Generic;

    public class TestItem
    {
        public Int32 ID { get; set; }
        public Int32 Weight { get; set; }
    }

    public class TestItemPartition
    {
        public static IEnumerable<TestItemPartition> PartitionItems(IEnumerable<TestItem> items, Int32 weightPartitionLimit)
        {
            var weightSum = 0;
            var itemList = new List<TestItem>();
            var partitionNumber = 1;

            foreach (var item in items)
            {
                if (weightSum + item.Weight > weightPartitionLimit && itemList.Count > 0)
                {
                    // limit reached and at least one item is in the partition
                    yield return new TestItemPartition(partitionNumber++, weightSum, itemList);
                    // re-initialize for next partition.
                    weightSum = 0;
                    itemList = new List<TestItem>();
                }
                // limit not reached, or a first single item exceeds the partition limit.
                // add item and increase weight sum.
                weightSum += item.Weight;
                itemList.Add(item);
            }
            // return partition for the last remaining items (if any).
            if (itemList.Count > 0)
                yield return new TestItemPartition(partitionNumber, weightSum, itemList);
        }

        public int PartitionNumber { get; private set; }
        public Int32 TotalWeight { get; private set; }
        public int TotalItems 
        {
            get { return _items.Count(); }
        }
        public IEnumerable<TestItem> Items
        {
            get { return _items; }
        }

        private TestItemPartition(int number, Int32 totalWeight, List<TestItem> items)
        {
            PartitionNumber = number;
            TotalWeight = totalWeight;
            _items = items;
        }
        private List<TestItem> _items;
    }

    class Program
    {
        public static void Main(params string[] args)
        {
            var items = new[] {
                new TestItem { ID = 1, Weight = 10  },
                new TestItem { ID = 2, Weight = 120 },
                new TestItem { ID = 3, Weight = 30  },
                new TestItem { ID = 4, Weight = 70  },
                new TestItem { ID = 5, Weight = 60  },
                new TestItem { ID = 6, Weight = 10  }
            };

            foreach (var partition in TestItemPartition.PartitionItems(items, 100))
                Console.WriteLine(
                    "#{0} - {1} items of total weight {2}.", 
                    partition.PartitionNumber, 
                    partition.TotalItems, 
                    partition.TotalWeight);

            Console.WriteLine("done");
            Console.ReadLine();
        }
    }
}

Answer 2

I like the answer by Alex very much. But a slightly more efficient Grouper can be made - by that I do not mean code, but 'fuller' groups. As is, it stops adding to a Partition when the next item's weight would cause it to exceed the desired limit.

For example, given a group with items {0, 1, 2} in it, item #3 may cause it to be overweight, but item 14 might still fit. Using a test data set of 200 items, the code below reduced the number of groups by s fair degree. If these are cartons of stuff to be shipped, the difference in handling and cartons alone might be noteworthy.¹ If you are creating groups almost as soon as the total weight exceeds 100, it probably won't matter (smaller datasets have fewer combinations).

The following iterates the items list, adding the next item until the remaining free space is less than that of the heaviest item. Then it picks an item with the closest weight to try and fill the current carton/group.² It might fail if all that is left are much lighter items, in which case it continues.

In order to scan the list over and over, I added a bool Grouped property to mark which ones have been grouped. (There almost certainly is something similar somewhere in the real code). I tried to do without it, but it helps assure everything gets grouped but only once. This version now uses a Groups class but it is just a convenience.

FooItem is simply TestItem + an int GroupID property.

public class FooGroup
{
    public List<FooItem> Items { get; private set; }
    public int ID { get; private set; }

    public FooGroup(int ndx)
    {
        Items = new List<FooItem>();
        ID = ndx;
    }

    public void Add(FooItem f)
    {
        Items.Add(f);
    }

    public void AddRange(FooItem[] f)
    {
        foreach (FooItem ff in f)
        {
            this.Add(ff);
        }
    }

    public int Count()
    {
        return Items.Count;
    }

    public int TotalWeight()
    {
        return Items.Sum(w => w.Weight);
    }

    public override string ToString()
    {
        return String.Format("ID: {0} Wt: {1}", 
            ID.ToString(), this.TotalWeight().ToString());
    }  
}

For the test items, rather than purely random values, I used random numbers of set values. I have no idea how well these represent the real world:

Random r = new Random();
int[] wts = {20,  25, 30, 35, 40, 45};    // Item weights
List<FooItem> fooList = new List<FooItem>();

for (int n = 1; n <= 200; n++)
{ 
    fooList.Add(new FooItem(n, 
         wts[ r.Next(6)]));
}

The grouping procedures:

private IEnumerable<FooGroup> GroupFooItems(List<FooItem> foo, 
              Int32 weightLimit, int Grp = 0)
{
    // temp copy of the list - wasteful, but
    // allows us to remove packed items
    List<FooItem> ftmp = new List<FooItem>(foo);

    while ((ftmp.Count > 3) && (ftmp.Sum(w => w.Weight) > weightLimit))
    {
        FooGroup tmp = NewFooGroup(ftmp, weightLimit, ++Grp);
        // could also remove where GroupID != -1
        ftmp.RemoveAll(r => tmp.Items.Contains(r));
        yield return tmp;
     }

    // there can be stuff left over - dump it into a final group
    if (ftmp.Count > 0)
    { 
       FooGroup grp = new FooGroup(-1);
       grp.AddRange(ftmp.ToArray());
       yield return grp;
    }
}

Iterate items and put them in a group:

private FooGroup NewFooGroup(List<FooItem> foo, 
           Int32 weightLimit, int nextGrp)
{
    FooGroup grp = new FooGroup(nextGrp);
    int FitWt = (weightLimit - 45);       // 45 is max wt in test set

    // the find best fit below might have "looked ahead"
    // and used the current one, so filter those out
    foreach (FooItem f in foo.Where( g => g.GroupID == -1))
    {

        if ((grp.TotalWeight() + f.Weight) < weightLimit)
        {
            f.GroupID = nextGrp;
            grp.Add(f);
        }

        // full enough that one more item could fill
        if (grp.TotalWeight() >= FitWt)
        {
            int wtThreshold = (weightLimit - grp.TotalWeight());
            // find items that fit ordered by wt
            List<FooItem> xfoo = foo.Where(
                w => (w.Weight <= wtThreshold) & (w.GroupID == -1)
                            ).OrderByDescending(w => w.Weight).ToList();

            // pack up the best fit
            if (xfoo.Count > 0)
            {
                xfoo[0].GroupID = nextGrp;
                grp.Add(xfoo[0]);
            }
        }
    }
    return grp;
}

Test and comparison code (using the 200 items from above):

// use TestItemPartition-er for comparison
var Partitions = TestItemPartition.PartitionItems(fooList, 100).ToList();          

// grouping results
var myGrps = GroupFooItems(fooList, 100).ToList();

I have lots of code to iterate and collect metrics like Waste Factor, count of light weights etc, check that everything went into a group etc etc etc. This is redacted for brevity.

Sample output:

* RESULTS *
Partitions: 75, Groups: 65
Perfect Packs: Partitions: 14, Groups: 55
Packs < 75: Partitions: 10, Groups: 0
Waste Factor: Partitions: 15.1%, Groups: 2.1
Details:
Grp # 00: Part Ct: 3 TWt 090 || Grp Ct: 3 TWt: 090
Grp # 01: Part Ct: 2 TWt 080 || Grp Ct: 3 TWt: 100
Grp # 02: Part Ct: 3 TWt 100 || Grp Ct: 3 TWt: 100
Grp # 03: Part Ct: 3 TWt 090 || Grp Ct: 3 TWt: 100
Grp # 04: Part Ct: 3 TWt 095 || Grp Ct: 3 TWt: 100
Grp # 05: Part Ct: 3 TWt 100 || Grp Ct: 3 TWt: 100

The metrics were originally to determine if my method improved on that of Alex enough to bother posting. They are now doing rather different things that comparisons are not very valid.

The first metric is the number of cartons/groups they fit into, and the most important. Perfect packs are those that equal 100 exactly (it is meaningless shipping wise as is the number of light cartons). Waste Factor is the sum of the unused capacity in each carton/group divided by the total items weight.

They both do a decent job, given what little we know of the nature of the weights and item list size. Smaller starting lists (e.g. 20 items) are less efficient because there are fewer chances to make perfect packs.

While the revision does try and fill each group to exactly 100 (or whatever the weightLimit is) it is more of a good-fit rather than best fit sort of thing: the items in the imperfect groups could very well be repacked differently into fewer groups. With the test data the gains would be minimal as only 10 of 65 might be able to be packed more efficiently.

---

¹ The nature of the data may well play into the result. If the random weights used are not representative of the actual item weight ranges, the actual results could be quite different. We of course, have no idea.

² That said this still is not any sort of best-fit algorithm: when item #4 won't fit it only checks to see if another will fit not how well any of them fit.