Get all pairs in a list using LINQ

13,379

Solution 1

Slight reformulation of cgeers answer to get you the tuples you want instead of arrays:

var combinations = from item1 in list
                   from item2 in list
                   where item1 < item2
                   select Tuple.Create(item1, item2);

(Use ToList or ToArray if you want.)

In non-query-expression form (reordered somewhat):

var combinations = list.SelectMany(x => list, (x, y) => Tuple.Create(x, y))
                       .Where(tuple => tuple.Item1 < tuple.Item2);

Both of these will actually consider n2 values instead of n2/2 values, although they'll end up with the correct answer. An alternative would be:

var combinations = list.SelectMany((x, i) => list.Skip(i + 1), (x, y) => Tuple.Create(x, y));

... but this uses Skip which may also not be optimized. It probably doesn't matter, to be honest - I'd pick whichever one is most appropriate for your usage.

Solution 2

Calculate the Cartesian product to determine all the possible combinations.

For example:

var combinations = from item in list
                   from item2 in list
                   where item < item2
                   select new[] { item, item2 };

You can find more information about calculating a cartesian product using LINQ here:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

You can then convert it to a collection of Tuple objects.

var pairs = new List<Tuple<int, int>>();
foreach (var pair in combinations)
{
    var tuple = new Tuple<int, int>(pair[0], pair[1]);
    pairs.Add(tuple);
}

Or in short:

var combinations = (from item in list
                    from item2 in list
                    where item < item2
                    select new Tuple<int, int>(item, item2)).ToList();

Solution 3

You could solve it like this:

 var list = new[] { 1, 2, 3, 4 };

 var pairs = from l1 in list
             from l2 in list.Except(new[] { l1 })
             where l1 < l2
             select new { l1, l2 };

 foreach (var pair in pairs)
 {
    Console.WriteLine(pair.l1 + ", " + pair.l2);
 }
Share:
13,379

Related videos on Youtube

dilbert
Author by

dilbert

Updated on June 04, 2022

Comments

  • dilbert
    dilbert almost 2 years

    How do I get all possible pairs of items in a list (order not relevant)?

    E.g. if I have

    var list = { 1, 2, 3, 4 };
    

    I would like to get these tuples:

    var pairs = {
       new Tuple(1, 2), new Tuple(1, 3), new Tuple(1, 4),
       new Tuple(2, 3), new Tuple(2, 4)
       new Tuple(3, 4)
    }
    
  • stakx - no longer contributing
    stakx - no longer contributing over 12 years
    1. This will create an enumerable of lists. Is that really what you meant? Why not just select Tuple.Create(item, item2)? 2. This will result in duplicate pairs, e.g. (1,4) and (4,1). Not sure if that's what the OP wants, but it doesn't look like it.
  • Mikael Östberg
    Mikael Östberg over 12 years
    It will also create (1,1), which is not stated in the OPs example and is not a pair. But I wonder if the the (1,4) and (4,1) thing is important.
  • Mikael Östberg
    Mikael Östberg over 12 years
    Jon, this will create the Tuple (1,1), which is not a pair.
  • Iarek
    Iarek over 12 years
    @stakx @Mikael All the duplicates can be filtered out by where item < item2.
  • Christophe Geers
    Christophe Geers over 12 years
    Thx for the feedback. Updated my answer to filter out the duplicates.
  • Mikael Östberg
    Mikael Östberg over 12 years
    @Laroslav Only if the items are in order to begin with, right?
  • stakx - no longer contributing
    stakx - no longer contributing over 12 years
    @Mikael, I don't think so, since if the predicate fails for one combination, it will succeed for the other (where the items are swapped around).
  • Mikael Östberg
    Mikael Östberg over 12 years
    @cgeers, you are still selecting an array mate. Your result will be IEnumberable<anononymous[]>
  • dilbert
    dilbert over 12 years
    Thanks, this is the best solution. (but, did you mean Skip(x.index + 1)?)
  • Mikael Östberg
    Mikael Östberg over 12 years
    Yes, the Except(..) thing is unnecessary since the where clause takes care of that.