Get all combinations from 2D array

Question

I have a 2d array, for which I want to get all possible combinations. But I'm getting stuck on how to do this. My data array looks like this:

var data = new string[][]
            {
                new string[] {"pa", "ga", "ka"},
                new string[] {"pb", "gb", "kb"}
            };

My expected output is something like this:

pa ga ka
pa ga kb
pa gb ka
pa gb kb
pb ga ka
pb ga kb
pb gb ka
pb gb kb

The order is also important. For example I can't make the combination ga pa ka. As the first item needs to start with p, second with g, and third with k. Therefore I can not use the cartesian product.

Note: In this example I have two rows. It could also be possible that I have more rows.

In particular, look at [Eric Lippert's answer](https://stackoverflow.com/a/3098381/106159) (and read the blog he mentioned, if you're interested in all the gory details). — Matthew Watson, Aug 05 '19 at 09:08
Are you sure it's a duplicate? In my example I have only two rows to keep it easy. But it's also possible I have more rows. — 1408786user, Aug 05 '19 at 09:20
I'm pretty sure - Eric's answer takes in an `IEnumerable>`, which means you can pass any number of arrays to it. — Matthew Watson, Aug 05 '19 at 09:37
The order is also important for me. For example with Eric's answer I get from var data = new string[][] { new string[] {"1", "2", "3"}, new string[] {"x", "y", "z"} }; var x = data.CartesianProduct(); the combination of 1y. Which can not be used in my situation. — 1408786user, Aug 05 '19 at 09:39

score 1 · Accepted Answer · answered Aug 05 '19 at 09:46

You can use Eric Lippert's solution,but you will need to transpose your input first.

Here's a transpose method, written by u/recursive:

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    IEnumerable<IEnumerable<T>> @this)
{
    var enumerators = @this.Select(t => t.GetEnumerator())
       .Where(e => e.MoveNext());

    while (enumerators.Any())
    {
        yield return enumerators.Select(e => e.Current);
        enumerators = enumerators.Where(e => e.MoveNext());
    }
}

Here's Eric Lippert's combinations generator, lifted from here:

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 })
    );
}

Putting it all together:

static void Main()
{
    var data = new string[][]
    {
        new string[] {"pa", "ga", "ka"},
        new string[] {"pb", "gb", "kb"}
    };

    var transposed = Transpose(data);

    foreach (var comb in CartesianProduct(transposed))
    {
        Console.WriteLine(string.Join(", ", comb));
    }
}

The output from this is:

pa, ga, ka
pa, ga, kb
pa, gb, ka
pa, gb, kb
pb, ga, ka
pb, ga, kb
pb, gb, ka
pb, gb, kb

Which is your specified requirement.

score 0 · Answer 2 · answered Aug 05 '19 at 09:45

var data = new string[][]
        {
            new string[] {"pa", "ga", "ka"},
            new string[] {"pb", "gb", "kb"}
        };
    foreach(var first in data[0])
    {
        foreach(var second in data[1])
        {
            List<string> list = new List<string>(data[1]);
            list.Remove(second);
            var arrayList=list.ToArray();
            string[] myArray = new string[3];
            myArray[0] = first;
            myArray[1] = arrayList[0];
            myArray[2] = arrayList[1];
            Console.WriteLine("{0}", string.Join(" ", myArray));            
        }
    }

Get all combinations from 2D array

2 Answers2