Получить все возможные отдельные тройки с помощью 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 (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

UPDATE: Я использовал этот вопрос в качестве предмета серии статей, начиная 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 х 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); 
    } 
} 

И мы сделали. Мы создали только столько последовательностей, сколько нам нужно. (Хотя мы сделали много заданных операций, чтобы добраться туда, но операции с множеством были дешевыми.) Дело здесь в том, что понимание того, как работает этот алгоритм, чрезвычайно поучительно. Рекурсивное программирование на неизменяемых структурах - это мощный инструмент, который многие профессиональные программисты не имеют в своей панели инструментов.

Answer 2

Вы можете сделать это следующим образом:

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: Спасибо Эрик Липперт для упрощения ответ!

Answer 3

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