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

Question

我有一个包含这些值的列表:{1、2、3、4、5、6、7}。我希望能够检索三个的独特组合。结果应该是这样的:

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

我已经有 2 个 for 循环可以做到这一点:

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

但是由于我正在学习 LINQ，我想知道是否有更聪明的方法来做到这一点？

Answer 1

更新:我用这个问题作为开始 here 的一系列文章的主题;我将在该系列中介绍两种略有不同的算法。感谢您提出很好的问题!

---

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

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

在这样做的同时，过滤掉第二个不大于第一个，第三个不大于第二个的任何地方。这执行 7 x 7 x 7 过滤操作，这不是很多，但是如果你试图从三十个元素中获得十个元素的排列，那就是 30 x 30 x 30 x 30 x 30 x 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);
  }
}

我们完成了。我们只生成了实际需要的序列。 (虽然我们已经做了很多集合操作来达到这个目的，但是集合操作很便宜。)这里的重点是理解这个算法是如何工作的是非常有启发性的。不可变结构的递归编程是许多专业程序员的工具箱中没有的强大工具。