Create Combinations according to the position in c# list

Question

I have a list

    var list = new List<record>{
    new record{ flashid = 450, position = 5, value = "a"},
    new record{ flashid = 450, position = 6, value = "b"},
    new record{ flashid = 450, position = 7, value = "c"},
    new record{ flashid = 450, position = 7, value = "d"},
    new record{ flashid = 450, position = 7, value = "e"},
    new record{ flashid = 450, position = 8, value = "f"},
    new record{ flashid = 450, position = 9, value = "g"}
}

I have 3 records with position as 7 with different value. from the above list, I need to create a string for each combination according to the position from 1 to 10. for missing position values we can have any temporary character. So, the desired output will be

["....abcfg.","....abdfg.","....abefg."]

we can have any special character in the place of dot.

Thanks

Please show any work you've done previously, and any research. For instance, this is generally referred to as a cartesian product, as in this question: [Is there a good LINQ way to do a cartesian product?](https://stackoverflow.com/q/4073713). — Heretic Monkey, Jun 27 '18 at 02:31
Possible duplicate of [LINQ implementation of Cartesian Product with pruning](https://stackoverflow.com/questions/6948019/linq-implementation-of-cartesian-product-with-pruning) — Rodrigo Rodrigues, Jun 27 '18 at 03:36

Slava Utesinov · Accepted Answer · 2018-06-27T09:32:25.687

Sure, you can solve this problem, as described at links from comments to your question, But, at this case, you should do tedious work - to write a lot of repeatable code like:

var answer = (from pos1 in list.Where(x => x.position == 1)
              from pos2 in list.Where(x => x.position == 2)
              from pos3 in list.Where(x => x.position == 3)
              ....
              from pos10 in list.Where(x => x.position == 10)
              select pos1.value + pos2.value + pos3.value + ... + pos10.value
             ).ToList();

So, each time, when you need to change number of possible positions you should add or remove corresponding lines of code. Instead, you can try recursive approach. Former solution is not dynamic - you should know number of positions in advance at compile time, whereas second solution can be simple tuned at run time via limit variable changing.

static int limit = 10;

static void Recursive(record record, List<string> bag, 
    Stack<record> stack, List<record> list)
{
    stack.Push(record);
    if (record.position == limit)
    {
        var temp = new StringBuilder();
        foreach (var item in stack)
            temp.Insert(0, item.value);
        bag.Add(temp.ToString());
    }
    else            
        foreach (var item in list.Where(x => x.position == record.position + 1))
            Recursive(item, bag, stack, list);
    stack.Pop();            
}

static List<string> Solve(List<record> list)
{
    for (var i = 1; i <= limit; i++)
        if (!list.Any(x => x.position == i))
             list.Add(new record { position = i, value = "." });

    var bag = new List<string>();
    var stack = new Stack<record>();
    foreach (var record in list.Where(x => x.position == 1))
        Recursive(record, bag, stack, list);

    return bag;
}

Usage:

var list = new List<record>
{
    new record { flashid = 450, position = 5, value = "a"},
    new record { flashid = 450, position = 6, value = "b"},
    new record { flashid = 450, position = 7, value = "c"},
    new record { flashid = 450, position = 7, value = "d"},
    new record { flashid = 450, position = 7, value = "e"},
    new record { flashid = 450, position = 8, value = "f"},
    new record { flashid = 450, position = 9, value = "g"}
};

var answer = Solve(list);       
Console.WriteLine("[" + string.Join(", ", answer) + "]");       
//output: [....abcfg., ....abdfg., ....abefg.]

Thanks @Slava. This is what I am looking for. – Nalluri Jun 27 '18 at 13:39 — Nalluri, Jun 27 '18 at 13:39

arekzyla · Answer 2 · 2018-06-27T13:03:02.953

If you would like to have a pure LINQ solution you can try the following. First of all extend your record list so that it contains each missing position:

var extendedList = Enumerable
    .Range(1, 10)
    .GroupJoin(list, n => n, r => r.position, (n, g) => g
        .DefaultIfEmpty(new record { flashid = 450, position = n, value = "." }));

This basically goes through range from 1 to 10 and for each number corresponding to position matches and groups records. If a group doesn't contain any matching value so that's when a position is missing there is created a default record with temporary character. So the result looks like this:

record[10][] 
{ 
    record[] 
    { 
        record { flashid=450, position=1, value="." } 
    },
    (...)
    record[] 
    { 
        record { flashid=450, position=5, value="a" } 
    },
    (...)
    record[] 
    { 
        record { flashid=450, position=7, value="c" },
        record { flashid=450, position=7, value="d" },
        record { flashid=450, position=7, value="e" } 
    },
    (...)
},

Now to generate all possible values you can try this:

var result = extendedList
    .Aggregate(Enumerable.Repeat("", 1), (a, c) => a
        .SelectMany(b => c
            .Select(d => b + d.value)));

Each Aggregate iteration transforms sequence of words into another sequence of words with added single character from characters group in current position. So it goes like this:

0. {""}
1. {"."}
2. {"."}
3. {".."}
4. {"..."}
5. {"....a"}
6. {"....ab"}
7. {"....abc", "....abd", "....abe"}
8. {"....abcf", "....abdf", "....abef"}
9. {"....abcfg", "....abdfg", "....abefg"}
10. {"....abcfg.", "....abdfg.", "....abefg."}

You can try it here: https://dotnetfiddle.net/JCgYFP

Create Combinations according to the position in c# list

2 Answers2