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

Question

我有一个List包含这些值:{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

更新:我用这个问题作为从这里开始的一系列文章的主题; 我将在该系列中介绍两种略有不同的算法.谢谢你这个好问题!

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

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

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

我们已经完成了.我们只生成了实际需要的序列.(虽然我们已经完成了大量的设置操作,但设置操作很便宜.)这里的要点是理解这种算法的工作方式非常有启发性.对不可变结构的递归编程是许多专业程序员在其工具箱中没有的强大工具.