C# algorithm for figuring out different possible combinations...

Question

I have 10 boxes, each box can hold one item from a group/type of items, each 'group' type only fits in one of the 10 box types. The item pool can have n number of items. The groups have completely distinct items. Each item has a price, i want an algorithm that will generate all the different possibilities, so i can figure out different price points vs custom rank/weight assignment to each of the items, based on item attributes.

so a smaller picture of the problem

BOX A - can have item 1,2,3,4 in it

BOX B - can have item 6,7,8,9,10,11,12

BOX C - can have item 13,15,16,20,21

More Detail
The solution would be a set of BOX A, BOX B, AND BOX C, having the greatest rank based on the set of boxes. Each box can only contain ONE of the designated items for that box. An item is an object, the object has 3 attributes(firmness, elasticity, strength). Each attribute can have 1-100 for a score. The goal is to enter a weight for each attribute, then the logic will run through ALL items and determine the top ranked item combinations based on the weights for each attribute. I have used 3 attributes for each item for ease of explanation, but items can have about 10 different attributes.

The items are stored in a db, they have a column which denotes which box they can go in. All box types are stored in an array, and I can put the items in a generic list. Anyone see a straightforward way to do this.

I have tried doing 10 nested foreach's to see if i could find a simpler way. The nested loops will take MANY hours to run. the nested for each's basically pull all combinations, then calculate a rank for each combination, and store the top 10 ranked combination of items for output

Answer 1

I have used an outstanding C# library for permutations and combinatorics.

It provides efficient algorithms for this class of problem.

Answer 2

Not sure if this was what you were looking for, but based on what I can infer from your question, using LINQ will be a lot simpler to code. Here's my guesstimate of what the answer should be:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    public class Box
    {
        public string Id { get; set; }
        public List<Item> Items {get;set;}
    }

    public class Item
    {
        public int Id { get; set; }

        public int Firmness { get; set; }
        public int Elasticity { get; set; }
        public int Strength { get; set; }
        public double Price { get; set; }

        public int FirmnessWt { get; set; }
        public int ElasWt { get; set; }
        public int StrWt { get; set; }

        public int ItemScore
        {
            get
            {
                return
                    (Firmness * FirmnessWt) +
                    (Elasticity * ElasWt) +
                    (Strength * StrWt);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // set the rankings
            int firmnessWt = 20;
            int elasWt = 40;
            int strWt = 80;

            // generate the items
            Item item1 = new Item { Id = 1, Elasticity = 1, Firmness = 4, Strength = 2, ElasWt=elasWt, FirmnessWt=firmnessWt, StrWt=strWt };
            Item item2 = new Item { Id = 2, Elasticity = 2, Firmness = 3, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item3 = new Item { Id = 3, Elasticity = 3, Firmness = 2, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item4 = new Item { Id = 4, Elasticity = 4, Firmness = 1, Strength = 3, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            Item item6 = new Item { Id = 6, Elasticity = 1, Firmness = 5, Strength = 2, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item7 = new Item { Id = 7, Elasticity = 1, Firmness = 4, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item8 = new Item { Id = 8, Elasticity = 1, Firmness = 3, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item9 = new Item { Id = 9, Elasticity = 2, Firmness = 2, Strength = 3, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item10 = new Item { Id = 10, Elasticity = 2, Firmness = 3, Strength = 2, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item11 = new Item { Id = 11, Elasticity = 2, Firmness = 2, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item12 = new Item { Id = 12, Elasticity = 3, Firmness = 6, Strength = 1, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            Item item13 = new Item { Id = 13, Elasticity = 3, Firmness = 5, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item15 = new Item { Id = 15, Elasticity = 2, Firmness = 4, Strength = 5, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item16 = new Item { Id = 16, Elasticity = 3, Firmness = 2, Strength = 5, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item20 = new Item { Id = 20, Elasticity = 3, Firmness = 1, Strength = 7, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };
            Item item21 = new Item { Id = 21, Elasticity = 3, Firmness = 1, Strength = 4, ElasWt = elasWt, FirmnessWt = firmnessWt, StrWt = strWt };

            // populate the 3 boxes with the generated items
            List<Box> boxes = new List<Box>
            {
                new Box
                {
                    Id = "A",
                    Items = new List<Item> { item1, item2, item3, item4 }
                },
                new Box
                {
                    Id="B",
                    Items = new List<Item> { item6, item7, item8, item9, item10, item11, item12 }
                },
                new Box
                {
                    Id="C",
                    Items = new List<Item> { item13, item15, item16, item20, item21 }
                }
            };

            // calculate top candidate for firmness
            List<Item> items = boxes.SelectMany(c => c.Items).ToList();

            Item firmnessCandidate = items.OrderByDescending(a => a.Firmness).First();

            // calculate top candidate for elasticity
            Item elasticityCandidate = items.OrderByDescending(b => b.Elasticity).First();


            // calculate top candidate for strength
            Item strengthCandidate = items.OrderByDescending(c => c.Strength).First();

            // calculate top candidate by combined weight
            Item weightCandidate = items.OrderByDescending(w => w.ItemScore).First();

            Console.WriteLine("Firmness - id:" + firmnessCandidate.Id.ToString() + ", score: " + firmnessCandidate.Firmness.ToString());
            Console.WriteLine("Elasticity - id:" + elasticityCandidate.Id.ToString() + ", score: " + elasticityCandidate.Elasticity.ToString());
            Console.WriteLine("Strength - id:" + strengthCandidate.Id.ToString() + ", score: " + strengthCandidate.Strength.ToString());
            Console.WriteLine("Item score - id:" + weightCandidate.Id.ToString() + ", score: " + weightCandidate.ItemScore.ToString());

            Console.ReadLine();
        }
    }
}

HTH...

Answer 3

It sounds like you just need to get the "best" item from each box, as adding the scores of the best item in each group will give the best overall total. If so, you should be able to do this all in the database with a decent query or in a simple LINQ-to-objects query on the client side if desired. Since I'm not an SQL person, I'll just go with the client approach. Using the obvious definition for the Item class:

public static double Score<T>(T item, IEnumerable<Weighting<T>> weights)
{
    return weights.Aggregate(0.0, (p, w) => p + w.Apply(item));
}

public static T MaxBy<T>(this IEnumerable<T> items, Func<T, double> selector)
{
    double curMax = double.MinValue;
    T curItem = default(T);
    foreach (T i in items)
    {
        double curValue = selector(i);
        if (curValue > curMax) 
        {
            curMax = curValue;
            curItem = i;
        }
    }
    return curItem;
}

public class Weighting<T>
{
    public Weighting(double weight, Func<T, double> attributeSelector)
    {
        _weight = weight;
        _attributeSelector = attributeSelector;
    }

    private readonly double _weight;
    private readonly Func<T, double> _attributeSelector;

    public double Apply(T item) { return _weight * _attributeSelector(item); }
}

Weighting<Item>[] weights = {new Weighting<Item>(1, i => i.Elasticity),
                             new Weighting<Item>(2, i => i.Firmness),
                             new Weighting<Item>(.5, i => i.Strength)};

var hsQuery = from i in allItems
              group i by i.Box into boxItems
              select boxItems.MaxBy(bi => Score(bi, weights));

I imagine there's a clever way to make the weighted score be a calculated column in an SQL query that you can then group by box where score = max(score) and get the result directly from the database.