List of list iteration(all possible one direction combination)

Question

I have a List<List<string>> representing a grid of rows and columns (the count of each is dynamic).

I need to iterate over the items and display all possible combinations in one direction.

If I have the following items, for example:

var items = new List<List<string>>
{
    new List<string> {"A", "B", "C", "D"},
    new List<string> {"E", "F", "G", "H"},
    new List<string> {"I", "J", "K", "L"},
};

The output should be :

---> *ABCD-ABCH-ABCL-ABGD-ABGH-ABGL-ABKD-ABKH-ABKL-........... IJKL*.

How can I iterate over the list to achieve this result?

I would advise you to change your data structure, maybe use a *graph* to facilitate your searches and optimize your performance — Greggz, Sep 06 '18 at 15:46
Like you see [here](https://math.stackexchange.com/questions/846423/all-possible-combinations-from-a-matrix) it is not that simple to get all combinations. Maybe it is easier when you tell us why you want to achieve that. — Henrik Wilshusen, Sep 06 '18 at 15:47
in fact i'm trying to make a profanity advanced filtering , some self-made deep learning algorithm for an advanced word detection , something like tensor flow or ML.NET , Greggz you told me about graph , i'm not familiar with them , are they faster than lists ? what about binary trees or linked lists ? — , Sep 06 '18 at 15:53
if i able to done this last step of my algorithm , i can easily detect h@i , h@y , hay , haa@aay , h1 , hl , h| and ..... just for "Hi" word , no profanity could detect them !! after this step and some training , of course i'll release the code to the github — , Sep 06 '18 at 15:59
Can you explain the requirements more? Is it all combinations of length four considering all letters? Can your list(s) contain repeats, and if so are they counted as different letters? What does it mean by "all possible combinations in _one direction_"? — Sach, Sep 06 '18 at 16:13
Implementing a profanity filter is a lot more complex than this: Here's [one article](https://medium.com/radius-engineering/demystifying-data-science-why-profanity-isnt-always-profane-520434d4c503) that talks about some of the challenges — Mulan, Sep 06 '18 at 19:09
I note that the number of combinations grows extremely quickly. In this simple example there are only 81 combinations, but if you have 3 rows and 10 columns instead of 4 columns that's almost 60000 combinations, and 10 rows and 10 columns has ten trillion combinations. **The comments noting that this is probably a bad technique for solving your problem are correct**. — Eric Lippert, Sep 06 '18 at 21:35

score 1 · Answer 1 · answered Sep 06 '18 at 18:45

What you want is the Cartesian product of the transpose. So break it down. First let's take the transpose:

public static List<List<T>> Transpose(
  this List<List<T>> sequences)
{
  // TODO: throw if sequences is null
  // TODO: throw if sequences contains any null
  // TODO: throw if the sequences are not all the same length
  return Enumerable.Range(0, sequences[0].Count)
    .Select(i => 
      Enumerable.Range(0, sequences.Count)
      .Select(j => sequences[j][i])
      .ToList())
    .ToList();
  }

We can take the Cartesian Product from my answer here: https://stackoverflow.com/a/3098381/88656

And now the answer to your question is straightforward.

IEnumerable<string> combinations = items
  .Transpose()
  .CartesianProduct()
  .Select(sequence => string.Join("", sequence));

Remember, the way to solve these problems is to break down the problem into a workflow of more basic operations on sequences, and then compose extension methods together into the workflow.

Patrick · Answer 2 · 2018-09-07T08:21:15.657

-1

Another approach to this problem, if you need a combination of N unique elements, is to flatten the matrix:

var elementArray = items.SelectMany(x => x).ToList();

Which turns {{'A', 'B', 'C'}, {'D', 'E', 'F'}} into {'A', 'B', 'C', 'D', 'E', 'F'}

Then use the following LINQ extension taken from another question (place it anywhere in your project):

public static class Ex
{
    public static IEnumerable<IEnumerable<T>> DifferentCombinations<T> (this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } :
          elements.SelectMany((e, i) =>
            elements.Skip(i + 1).DifferentCombinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

Used as:

var combinations = elementArray.DifferentCombinations(4)
    .Select(
        l => string.Join("", l.ToArray())
    ).ToList();

In this case, it will combine up to a length of 4 (DifferentCombinations(4)).

edited Sep 07 '18 at 08:21

answered Sep 06 '18 at 16:23

Patrick

419
4
16

This solution is needlessly complicated and hard to follow; I have no idea if it is correct or not. Please don't just post code. **Explain why the code solves the user's problem**. The point is not just to solve people's specific problems, but to educate them about the technique so that they don't have to keep on coming back here to get their code written. – Eric Lippert Sep 06 '18 at 21:36
Garbage in, garbage out; I'll be improving my answer now I have time, today. To fully consider the people trying to find this in the future, the question should be heavily improved. – Patrick Sep 07 '18 at 07:58
The answer is now much better in terms of its pedagogy, but I don't think it answers the question that was asked. My understanding of the question is that the user is looking for all combinations of (item from column 1) x (item from column 2) x (item from column 3) x (item from column 4), but it looks like you are simply returning all combinations of items regardless of their column rank. – Eric Lippert Sep 07 '18 at 17:12

List of list iteration(all possible one direction combination)

2 Answers2