Get all possible distinct triples using LINQ

Question

I have a List contains these values: {1, 2, 3, 4, 5, 6, 7}. And I want to be able to retrieve unique combination of three. The result should be like this:

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,2,7}
{2,3,4}
{2,3,5}
{2,3,6}
{2,3,7}
{3,4,5}
{3,4,6}
{3,4,7}
{3,4,1}
{4,5,6}
{4,5,7}
{4,5,1}
{4,5,2}
{5,6,7}
{5,6,1}
{5,6,2}
{5,6,3}

I already have 2 for loops that able to do this:

for (int first = 0; first < test.Count - 2; first++)
{
  int second = first + 1;
  for (int offset = 1; offset < test.Count; offset++)
  {
    int third = (second + offset)%test.Count;
    if(Math.Abs(first - third) < 2)
      continue;
    List<int> temp = new  List<int>();
    temp .Add(test[first]);
    temp .Add(test[second]);
    temp .Add(test[third]);
    result.Add(temp );
  }
}

But since I'm learning LINQ, I wonder if there is a smarter way to do this?

Answer 1

UPDATE: I used this question as the subject of a series of articles starting here; I'll go through two slightly different algorithms in that series. Thanks for the great question!

---

The two solutions posted so far are correct but inefficient for the cases where the numbers get large. The solutions posted so far use the algorithm: first enumerate all the possibilities:

{1, 1, 1 }
{1, 1, 2 }, 
{1, 1, 3 }, 
...
{7, 7, 7}   

And while doing so, filter out any where the second is not larger than the first, and the third is not larger than the second. This performs 7 x 7 x 7 filtering operations, which is not that many, but if you were trying to get, say, permutations of ten elements from thirty, that's 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30, which is rather a lot. You can do better than that.

I would solve this problem as follows. First, produce a data structure which is an efficient immutable set. Let me be very clear what an immutable set is, because you are likely not familiar with them. You normally think of a set as something you add items and remove items from. An immutable set has an Add operation but it does not change the set; it gives you back a new set which has the added item. The same for removal.

Here is an implementation of an immutable set where the elements are integers from 0 to 31:

using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System;

// A super-cheap immutable set of integers from 0 to 31 ; 
// just a convenient wrapper around bit operations on an int.
internal struct BitSet : IEnumerable<int>
{
  public static BitSet Empty { get { return default(BitSet); } }
  private readonly int bits;
  private BitSet(int bits) { this.bits = bits; }
  public bool Contains(int item) 
  {
    Debug.Assert(0 <= item && item <= 31); 
    return (bits & (1 << item)) != 0; 
  }
  public BitSet Add(int item) 
  { 
    Debug.Assert(0 <= item && item <= 31); 
    return new BitSet(this.bits | (1 << item)); 
  }
  public BitSet Remove(int item) 
  { 
    Debug.Assert(0 <= item && item <= 31); 
    return new BitSet(this.bits & ~(1 << item)); 
  }
  IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
  public IEnumerator<int> GetEnumerator()
  {
    for(int item = 0; item < 32; ++item)
      if (this.Contains(item))
        yield return item;
  }
  public override string ToString() 
  {
    return string.Join(",", this);
  }
}

Read this code carefully to understand how it works. Again, always remember that adding an element to this set does not change the set. It produces a new set that has the added item.

OK, now that we've got that, let's consider a more efficient algorithm for producing your permutations.

We will solve the problem recursively. A recursive solution always has the same structure:

• Can we solve a trivial problem? If so, solve it.
• If not, break the problem down into a number of smaller problems and solve each one.

Let's start with the trivial problems.

Suppose you have a set and you wish to choose zero items from it. The answer is clear: there is only one possible permutation with zero elements, and that is the empty set.

Suppose you have a set with n elements in it and you want to choose more than n elements. Clearly there is no solution, not even the empty set.

We have now taken care of the cases where the set is empty or the number of elements chosen is more than the number of elements total, so we must be choosing at least one thing from a set that has at least one thing.

Of the possible permutations, some of them have the first element in them and some of them do not. Find all the ones that have the first element in them and yield them. We do this by recursing to choose one fewer elements on the set that is missing the first element.

The ones that do not have the first element in them we find by enumerating the permutations of the set without the first element.

static class Extensions
{
  public static IEnumerable<BitSet> Choose(this BitSet b, int choose)
  {
    if (choose < 0) throw new InvalidOperationException();
    if (choose == 0) 
    { 
      // Choosing zero elements from any set gives the empty set.
      yield return BitSet.Empty; 
    }
    else if (b.Count() >= choose) 
    {
      // We are choosing at least one element from a set that has 
      // a first element. Get the first element, and the set
      // lacking the first element.

      int first = b.First();
      BitSet rest = b.Remove(first);
      // These are the permutations that contain the first element:
      foreach(BitSet r in rest.Choose(choose-1))
        yield return r.Add(first);
      // These are the permutations that do not contain the first element:
      foreach(BitSet r in rest.Choose(choose))
        yield return r;
    }
  }
}

Now we can ask the question that you need the answer to:

class Program
{
  static void Main()
  {
    BitSet b = BitSet.Empty.Add(1).Add(2).Add(3).Add(4).Add(5).Add(6).Add(7);
    foreach(BitSet result in b.Choose(3))
      Console.WriteLine(result);
  }
}

And we're done. We have generated only as many sequences as we actually need. (Though we have done a lot of set operations to get there, but set operations are cheap.) The point here is that understanding how this algorithm works is extremely instructive. Recursive programming on immutable structures is a powerful tool that many professional programmers do not have in their toolbox.

Answer 2

You can do it like this:

var data = Enumerable.Range(1, 7);
var r = from a in data
        from b in data
        from c in data
        where a < b && b < c
        select new {a, b, c};
foreach (var x in r) {
    Console.WriteLine("{0} {1} {2}", x.a, x.b, x.c);
}

Demo.

Edit: Thanks Eric Lippert for simplifying the answer!