generate all possible combinations for a dynamic list of attributes with their values

Question

I struggle with generating all possible combinations for a List of Attributes with their possible values. What I would like to implement is a Method like this:

public List<Variant> generateAllPossibleVariants(List<Attribute> attributes)

The Attribute Class looks the following:

public class Attribute {
    public String Name { get; set; }
    public ICollection<String> PossibleValues { get; protected set; }
}

So imagine you have a list of 2 Attributes (while the count is dynamic) with their possible values:

attributeColor with possible Values of ( "red", "blue" )
attributeSize with possible values of ("XL", "L" )

Now my method should return a List of Variant while the Variant Class looks the following:

public class Variant
{
    public IDictionary<Attribute, string> AttributeValues { get; private set; }
}

Now my method should return a List of all combinations like the following:

List<Variant> :
    Variant.AttributeValues { attributeColor => "red", attributeSize => "XL" }
    Variant.AttributeValues { attributeColor => "red", attributeSize => "L" }
    Variant.AttributeValues { attributeColor => "blue", attributeSize => "XL" }
    Variant.AttributeValues { attributeColor => "blue", attributeSize => "L" }

This might help: http://stackoverflow.com/questions/4073713/is-there-a-good-linq-way-to-do-a-cartesian-product — Davin Tryon, Feb 23 '15 at 12:14
I really think this is why DB where made, if you store the data in the DB it will be much clearer how to store and pull it. but that's my opinion . — Liran, Feb 23 '15 at 12:29

score 0 · Answer 1 · answered Feb 23 '15 at 12:26

You are looking for cartesian product (with dynamic dimension).

One simple way to achieve it is using recursion on the dimension, and each time invoke cartesian product on the result of the recursion, and one of the dimensions.

Pseudo code:

genAllPossibilities(list attributes) //each element in attributes is a list
   if length(attributes) == 1:
        return attributes[0] //the only element, which is a list of one attribute
   else:
        curr = head(attributes) // first element in the list
        reminder = tails(attributes) // a list of all elements except the first
        return cartesianProduct(genAllPossibilities(reminder), curr)

cartesianProduct(list1, list2):
     l = new list
     for each x1 in list1:
         for each x2 in list2:
                l.append(new MyObject(x1,x2))
      return l

score 0 · Accepted Answer · answered Feb 23 '15 at 12:54

This is not an optimized code, but you can get the idea and clean it up yourself:

public void Main()
{
    var attr1 = new MyAttribute  { Name = "Colors", PossibleValues = new List<string> { "red", "blue" } };
    var attr2 = new MyAttribute  { Name = "Sizes", PossibleValues = new List<string> { "XL", "L" } };   
    var attr3 = new MyAttribute  { Name = "Shapes", PossibleValues = new List<string> { "qube", "circle" } };   
    var attrList = new List<MyAttribute> { attr1, attr2, attr3 };

    var result = attrList.Skip(1).Aggregate<MyAttribute, List<Variant>>(
        new List<Variant>(attrList[0].PossibleValues.Select(s => new Variant { AttributeValues = new Dictionary<MyAttribute, string> { {attrList[0], s} } })),
        (acc, atr) =>
        {
            var aggregateResult = new List<Variant>();

            foreach (var createdVariant in acc)
            {
                foreach (var possibleValue in atr.PossibleValues)
                {
                    var newVariant = new Variant { AttributeValues = new Dictionary<MyAttribute, string>(createdVariant.AttributeValues) };
                    newVariant.AttributeValues[atr] = possibleValue;
                    aggregateResult.Add(newVariant);
                }
            }

            return aggregateResult;
        });
}

public class MyAttribute
{
    public string Name { get; set; }
    public ICollection<string> PossibleValues { get; set; }
}

public class Variant
{
    public IDictionary<MyAttribute, string> AttributeValues { get; set; }
}

generate all possible combinations for a dynamic list of attributes with their values

2 Answers2