使用LINQ获取所有可能的不同三元组

UPDATE：我用这个问题作为从这里开始的一系列文章的主题；我将在该系列中介绍两种略有不同的算法。谢谢你的提问！

到目前为止发布的两个解决方案是正确的，但对于数字变大的情况来说效率低下。到目前为止发布的解决方案使用算法：首先列举所有可能性：

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

在这样做的同时，过滤掉任何第二个不大于第一个，第三个不大于第二个的地方。它执行7 x 7 x 7的过滤操作，数量不多，但如果你试图从30个元素中获得10个元素的排列，那就是30 x 30 x 30×30 x 30 x 30 x 30 x 30。你可以做得更好。

我将按如下方式解决这个问题。首先，生成一个数据结构，它是一个有效的不可变集。让我非常清楚什么是不可变集，因为您可能不熟悉它们。你通常认为一个集合是你添加项目和从中删除项目的东西。一个不可变集合有一个Add操作，但它不改变集合；它会返回一个新的集合，其中包含添加的项。拆卸时也是如此。

这里是一个不可变集合的实现，其中元素是从0到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);
  }
}

仔细阅读此代码以了解其工作原理。同样，请始终记住，向该集合添加元素不会更改集合。它生成一个新的集合，该集合包含添加的项。

好吧，既然我们已经知道了，让我们考虑一个更有效的算法来产生你的排列。

我们将递归地解决这个问题。递归解决方案总是具有相同的结构：

• 我们能解决一个琐碎的问题吗？如果是，请解决它
• 如果没有，则将问题分解为多个较小的问题，并解决每个问题

让我们从琐碎的问题开始。

假设你有一个集合，你想从中选择零个项。答案很清楚：只有一个可能的置换有零个元素，那就是空集。

假设你有一个包含n个元素的集合，并且你想选择n个以上的元素。显然没有解决方案，甚至连空套都没有。

我们现在已经处理了集合为空或者所选元素的数量大于元素总数的情况，所以我们必须从至少有一个元素的集合中选择至少一个元素。

在可能的排列中，有些排列中有第一个元素，有些则没有。找到所有包含第一个元素的元素并生成它们。我们通过递归选择集合上的少一个元素来实现这一点，其中缺少第一个元素。

我们通过枚举没有第一个元素的集合的排列来找到那些而不是的集合中有第一个元素。

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

现在我们可以问你需要答案的问题：

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

我们完了。我们只生成了我们实际需要的那么多序列。（尽管我们已经做了很多集运算，但集运算很便宜。）这里的重点是，了解这种算法的工作原理非常有指导意义。不可变结构上的递归编程是许多专业程序员工具箱中没有的强大工具。

你可以这样做：

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

演示。

编辑：感谢Eric Lippert简化了答案！

var ints = new int[] { 1, 2, 3, 4, 5, 6, 7 };
var permutations = ints.SelectMany(a => ints.Where(b => (b > a)).
                        SelectMany(b => ints.Where(c => (c > b)).
                        Select(c => new { a = a, b = b, c = c })));