CODEWITHSUNDEEP
c#linqcombinations
user673679
user673679

Reputation: 1366

c# combinations with linq

I have an array of values, e.g. { 0, 1, 2 } which can be in one of two states { 0, 1 }.

Is there a simple way (perhaps using a linq query) to get a list of all combinations of { value, state } (where value is unique) so that I get results like:

{
{ { 0, 0 }, { 1, 0 }, { 2, 0 } },
{ { 0, 0 }, { 1, 0 }, { 2, 1 } },
{ { 0, 0 }, { 1, 1 }, { 2, 0 } },
{ { 0, 0 }, { 1, 1 }, { 2, 1 } },
{ { 0, 1 }, { 1, 0 }, { 2, 0 } },
{ { 0, 1 }, { 1, 0 }, { 2, 1 } },
{ { 0, 1 }, { 1, 1 }, { 2, 0 } },
{ { 0, 1 }, { 1, 1 }, { 2, 1 } },
}

The "value" array can be of varying size, but they can only ever be in one of two states.

(It's not a cartesian product exactly, and I'm not sure what term can be used to describe it, so don't know what to google).

Thanks!

Upvotes: 1

Views: 2034

Answers (4)

KeithS
KeithS

Reputation: 71565

It's a Cartesian product of Cartesian products:

var groups = from x in 
                (from v in values
                 from s in states
                 select new {v,s})
             group x by x.v into gx
             select gx;

var perms = from a in groups[0]
            from b in groups[1]
            from c in groups[2]
            select new {a,b,c};

The groups query produces a Lookup (conceptually a read-only Dictionary of IEnumerables) containing the simple Cartesian product of all values and states (6 elements), grouped by their value. Then, the second query produces a Cartesian product of the elements of the Cartesian product taken three at a time, one from each group in the Lookup.

To make this work with an unknown number of dimensions would be tricky; if you don't absolutely have to make it work that way I would avoid it. I think the most elegant way would be to define a set of extension methods for the System.Tuple generic classes:

public static Tuple<T1,T2> Append(this Tuple<T1> tuple, T2 addend)
{
   return Tuple.Create(tuple.Item1, addend);
}

public static Tuple<T1,T2, T3> Append(this Tuple<T1,T2> tuple, T3 addend)
{
   return Tuple.Create(tuple.Item1, tuple.Item2, addend);
}

...

Then, you can take these helpers and use them in a looped version of the second query:

var perms = from a in groups[0] select Tuple.Create(a);

foreach(var group in groups.Skip(1)) perms = from a in perms from b in group select a.Append(b);

This will produce an enumerable of Tuples of the required length, containing the elements of the anonymous type produced in the first query (which can be refactored to produce strongly-typed 2-item Tuples if you wish). You may have an issue with using the perms collection variable to refer to collections of ever-growing Tuples; this is the tricky part.

Upvotes: 3

Guffa
Guffa

Reputation: 700152

As the two states can be seen as bits, you can get the combinations by simply counting and converting the bits to items in an array:

int maxValue = 2;
int[][][] values = Enumerable.Range(0, 1 << maxValue).Select(n =>
  Enumerable.Range(0, maxValue + 1).Select(m =>
    new[] { m, (n >> (maxValue - m)) & 1 }
  ).ToArray()
).ToArray();

Upvotes: 0

Justin Morgan
Justin Morgan

Reputation: 30705

Maybe something like:

var lst1 = new List<int> { 0, 1, 2 };
var lst2 = new List<int> { 0, 1 };

lst1.ForEach(i => {
    Console.WriteLine("{");
    lst2.ForEach(j => Console.Write("{ " + i + "," + j + "}"));
    Console.WriteLine("}");
});

This won't really be in the format you want; you should build some kind of array(s) and then join it on "," and/or "}, {". This should give you the general idea, though.

Upvotes: 0

Muhammad Adeel Zahid
Muhammad Adeel Zahid

Reputation: 17784

try 

var values = new int[]{0,1,2};
var states = new int[]{0,1};

var permutations = from v in values
                   from s in states
                   select new {v,s}

you simply need a cross product of two arrays regardless of size of arrays

Upvotes: 2

Related Questions