How to go from iterative approach to recursive approach

Question

I have an iterative C# loop which fills out a checkboard pattern of up to 5 columns.

The values are paired, it's always a Headline and multiple Values for each column, and it's combining the values to a non-repetitative combination.

Starting with the simplest solution I could imagine, and after looking at it, I thought there must be a better approach to this problem by doing this recursively.

Below is an example of what I've tried so far:

 List<EtOfferVariant> variants = new List<EtOfferVariant>();

 _containers[0].Variant.ForEach(first =>
 {
     if (_containers.Count > 1)
     {
         _containers[1].Variant.ForEach(second =>
         {
             if (_containers.Count > 2)
             {
                 _containers[2].Variant.ForEach(third =>
                     {
                         EtOfferVariant va = new EtOfferVariant();
                         va.OfferVariant1Type = _containers[0].VariantKey;
                         va.OfferVariant1 = first;
                         va.OfferVariant2Type = _containers[1].VariantKey;
                         va.OfferVariant2 = second;
                         va.OfferVariant3Type = third;
                         va.OfferVariant3 = _containers[3].VariantKey;
                         variants.Add(va);
                     });
             }
             else
             {
                 EtOfferVariant va = new EtOfferVariant();
                 va.OfferVariant1Type = _containers[0].VariantKey;
                 va.OfferVariant1 = first;
                 va.OfferVariant2Type = second;
                 va.OfferVariant2 = _containers[1].VariantKey;
                 variants.Add(va);
             }
         });
     }
     else
     {
         EtOfferVariant va = new EtOfferVariant();
         va.OfferVariant1Type = _containers[0].VariantKey;
         va.OfferVariant1 = first;
         variants.Add(va);
     }
 });

The containers consist of a list of strings (the values) and a key (the headline).

It's a shortend version OfferVariant counts up to 5 in the real example.

I cant change the inital checkboard structure since its given by a existing database.

Below is an illustration of the data input and output for 2 containers consisting of:

Container 1:

Key: Pie
Values:
1. Raspberry
2. Strawberry

Container 2:

Key: Drink
Values:
1. Cola,
2. Coffee

The generated output would consist of 4 rows containing

edit due the fact its easyly missunderstood as its illustrated here

The Result will be a Row in a Database consisting of 4 columns

Column 1 | Column 2  | Column 3 | Column 4
Pie      | Raspberry | Drink    | Cola 
Pie      | Raspberry | Drink    | Coffee
Pie      | Strawberry| Drink    | Cola 
Pie      | Strawberry| Drink    | Coffee

EtOfferVariant is a ORM Poco containing those columns

From your example it looks like you are trying to create a cartesian product. In that case you can write a general algorithm where the number of sets in the product does not have to be fixed: http://stackoverflow.com/a/16996888/98607. However, this does not involve recursion. — Martin Liversage, Aug 20 '14 at 10:25

subkonstrukt · Accepted Answer · 2014-08-20T12:36:30.507

Thank you for your replies, Martin Liversage kinda guided me mental to it, tough it wasnt a pure cartesian product due the fact is was grouped to be flattend out latter and Cines approach gave me the final point in the right direction I solved this the following way now

in the first step I generate the inital rows for the first variant

    List<EtOfferVariant> row = new List<EtOfferVariant>();
    _containers.First().Variant.ForEach(o =>
    {
        row.Add(new EtOfferVariant() { OfferVariant1 = o, OfferVariant1Type = _containers.First().VariantKey });
    });
  return BuildVariants(row);

and then run it trough

  private List<EtOfferVariant> BuildVariants(List<EtOfferVariant> row, int containerIndex = 1)
    {
        List<EtOfferVariant> final = new List<EtOfferVariant>();
        row.ForEach(y =>
        {
            for (int i = 0; i < _containers[containerIndex].Variant.Count; i++)
            {
                var ret = MultiplyFromPrevious(y);
                FillByIndex(ret, _containers[containerIndex].Index, _containers[containerIndex].VariantKey, _containers[containerIndex].Variant[i]);
                final.Add(ret);
            }
        });
        containerIndex++;
        if (containerIndex < _containers.Count)
           return BuildVariants(final, containerIndex);
        return final;
    }

and thanks again to Cine

private EtOfferVariant MultiplyFromPrevious(EtOfferVariant variant)
{
    EtOfferVariant ret = new EtOfferVariant();
    ret.OfferVariant1 = variant.OfferVariant1;
    ret.OfferVariant2 = variant.OfferVariant2;
    ret.OfferVariant3 = variant.OfferVariant3;
    ret.OfferVariant4 = variant.OfferVariant4;
    ret.OfferVariant5 = variant.OfferVariant5;

    ret.OfferVariant1Type = variant.OfferVariant1Type;
    ret.OfferVariant2Type = variant.OfferVariant2Type;
    ret.OfferVariant3Type = variant.OfferVariant3Type;
    ret.OfferVariant4Type = variant.OfferVariant4Type;
    ret.OfferVariant5Type = variant.OfferVariant5Type;

    return ret;
}

I also seperated the column split into an own method, but it does nothing less then taking the index and map the values to the object, nothing special

thanks again everyone, this really loosend up the code

score 0 · Answer 2 · answered Aug 20 '14 at 11:38

I presume you just want to cut down on the duplicate code. In that case, just add data as you know it and add the variant at the end once it is built up. Only thing is, is that you need a copy constructor that copies the values from the previous runs.

List<EtOfferVariant> variants = new List<EtOfferVariant>();

_containers[0].Variant.ForEach(first =>
{
    EtOfferVariant va = new EtOfferVariant();
    va.OfferVariant1Type = _containers[0].VariantKey;
    va.OfferVariant1 = first;
    if (_containers.Count > 1)
    {
        _containers[1].Variant.ForEach(second =>
        {
            va = new EtOfferVariant(va);
            va.OfferVariant2Type = _containers[1].VariantKey;
            va.OfferVariant2 = second;
            if (_containers.Count > 2)
            {
                _containers[2].Variant.ForEach(third =>
                {
                    va = new EtOfferVariant(va);
                    va.OfferVariant3Type = third;
                    va.OfferVariant3 = _containers[3].VariantKey;
                    variants.Add(va);
                });
            } else 
            variants.Add(va);
        });
    } else
    variants.Add(va);
});

...

public EtOfferVariant(EtOfferVariant va){
   this.OfferVariant1Type = va.OfferVariant1Type;
   this.OfferVariant2Type = va.OfferVariant2Type;
   this.OfferVariant3Type = va.OfferVariant3Type;
   this.OfferVariant1 = va.OfferVariant1;
   this.OfferVariant2 = va.OfferVariant2;
   this.OfferVariant3 = va.OfferVariant3;
}

score 0 · Answer 3 · edited May 23 '17 at 11:49

If you first convert the dictionaries in the containers it seems you can get the wanted result by cartesian product.

var containers = new List<Dictionary<string, IEnumerable<string>>>
                    {
                        new Dictionary<string, IEnumerable<string>>() {{"Pie", new [] {"Raspberry", "Strawbery"}}},
                        new Dictionary<string, IEnumerable<string>>() {{"Drink", new [] {"Cola", "Coffee"}}},
                        new Dictionary<string, IEnumerable<string>>() {{"Bread", new [] {"Bagel", "Pretzel", "Scone"}}},
                    };

var flatten = containers.Select(dict => dict.SelectMany(c => c.Value.Select(v => new {type = c.Key, name = v})));

foreach (var combo in CartesianProduct(flatten))
{
    Console.WriteLine(string.Join(", ", combo.Select(c => c.type + ": " + c.name)));
}

Cartesian product method from https://stackoverflow.com/a/3098381/44620

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
            from accseq in accumulator 
            from item in sequence 
            select accseq.Concat(new[] {item})                         
        );
}

Output:

Pie: Raspberry, Drink: Cola, Bread: Bagel
Pie: Raspberry, Drink: Cola, Bread: Pretzel
Pie: Raspberry, Drink: Cola, Bread: Scone
Pie: Raspberry, Drink: Coffee, Bread: Bagel
Pie: Raspberry, Drink: Coffee, Bread: Pretzel
Pie: Raspberry, Drink: Coffee, Bread: Scone
Pie: Strawbery, Drink: Cola, Bread: Bagel
Pie: Strawbery, Drink: Cola, Bread: Pretzel
Pie: Strawbery, Drink: Cola, Bread: Scone
Pie: Strawbery, Drink: Coffee, Bread: Bagel
Pie: Strawbery, Drink: Coffee, Bread: Pretzel
Pie: Strawbery, Drink: Coffee, Bread: Scone

thank you i tried this approach before, tough i had troubles getting the aggregated values into the right columns that way, I've edited the question since my output seemed to be unclear — subkonstrukt, Aug 20 '14 at 12:54

How to go from iterative approach to recursive approach

3 Answers3