how to get the best way of grouping by product, including the average of records per Product-CodePudding

what I'm trying to do is grouping by product and ensure same product is scheduled to be counted on same days always, the daysScheduled can not be more than product types MILK,CHAIR,TABLE,TV = 4 product types and max scheduledDays would be 4, and the scheduledDays could be another input and the list of product as well

int daysScheduled = 2

IList<Product> products = new List<Product>();
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("TABLE", "789"));
products.Add(new Product("TABLE", "789"));
products.Add(new Product("TV", "567"));
products.Add(new Product("TV", "567"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));

BAD WAY OF GROUPING, because in the second day there are two products(9 records) and one of this could be moved to first day in order to have a better way of grouping(average of records), notice that is not possible to split products, if one this product is moved all records of this product should moved as well

   // DAY 1 => type of products=2, records=4 
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("TABLE", "789"));
products.Add(new Product("TABLE", "789"));

    // DAY 2 => type of products=2, records=9
products.Add(new Product("TV", "567"));
products.Add(new Product("TV", "567"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));

EXPECTED RESULT, because in average of records there are almost the same qty on each day

    // DAY 1 => type of products=3, records=6 
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("CHAIR", "456"));
products.Add(new Product("TABLE", "789"));
products.Add(new Product("TABLE", "789"));
products.Add(new Product("TV", "567"));
products.Add(new Product("TV", "567"));

    // DAY 2 => type of products=1, records=7
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));
products.Add(new Product("MILK", "123"));

pdta. keep the order in which the products were added

How should I do this? please help

CodePudding user response：

If I understand the task right, it is required to place N items of different types (number of types - X) into Z "days" so that one type of item would be placed in the same "day" and the number of items in "days" should be the same if possible and equal to N/Z.

Solution #1 is to group all items by type and then check all possible combinations of dividing those groups into Z "days" and peak the best result. The solution can give the most accurate result but is very expensive in terms of time - O(X^Z)

Solution #2 is to use Greedy algorithm. This algorithm is often used to solve optimization problems like that. It is not guaranteed that it will give the best possible result but its time complexity is much less. So, in the current task, we need to group items by type, sort them by the number of items in descending order, and then pick items until the number is less or equal to N/Z

var maxSize = products.Count / typeNumber;
var result = new List<List<Product>>();
var size = maxSize;
foreach (var itemsOfType in products
             .GroupBy(p => p.Type)
             .Select(g => g.ToList())
             .OrderByDescending(g => g.Count))
{
    if (size   itemsOfType.Count > maxSize)
    {
        result.Add(new List<Product>(itemsOfType.Count));
        size = 0;
    }
    result[^1].AddRange(itemsOfType);
    size  = itemsOfType.Count;
}