开发者

c# combinations with linq

开发者 https://www.devze.com 2023-02-19 12:18 出处:网络
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

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!


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.


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


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.


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();
0

精彩评论

暂无评论...
验证码 换一张
取 消