Làm thế nào để sử dụng LINQ để tìm tất cả các kết hợp của n mục từ một tập hợp các số?

Question

Tôi đang cố gắng viết một thuật toán để chọn tất cả các kết hợp của các giá trị n từ một tập hợp các số.

Ví dụ, với các thiết lập: 1, 2, 3, 7, 8, 9

Tất cả sự kết hợp của 2 giá trị từ tập là:

(1, 2), (1, 3), (1, 7), (1, 8), (1, 9), (2, 3), (2, 7), (2, 8), (2, 9), (3, 7), (3, 8), (3 , 9), (7, 8), (7, 9), (8, 9)

Và 3 là:

(1, 2, 3), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 7, 8), (1, 7, 9), (1, 8, 9), (2, 3, 7), (2, 3, 8), (2, 3, 9), (2, 7, 8), (2, 7, 9), (2, 8, 9), (3, 7, 8), (3, 7, 9), (3, 8, 9), (7, 8, 9)

v.v.

Tôi hiện đang sử dụng các phương pháp để mang lại các tập hợp kết hợp của các giá trị 2, 3 và 4, nhưng dường như với tôi điều này có thể được khái quát hóa trong truy vấn LINQ.

Cảm ơn sự giúp đỡ của bạn!

Answer 1

Cách sử dụng:

var results = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.DifferentCombinations(3); 

Code:

public static class Ex 
{ 
    public static IEnumerable<IEnumerable<T>> DifferentCombinations<T>(this IEnumerable<T> elements, int k) 
    { 
     return k == 0 ? new[] { new T[0] } : 
      elements.SelectMany((e, i) => 
      elements.Skip(i + 1).DifferentCombinations(k - 1).Select(c => (new[] {e}).Concat(c))); 
    } 
} 

Answer 2

Mặc dù câu trả lời ở trên là rất gọn gàng tôi đã đưa ra một giải pháp có thể được nhanh hơn nhiều tùy thuộc vào kích thước bộ sưu tập.

static class Combinations 
{ 
    private static void InitIndexes(int[] indexes) 
    { 
     for (int i = 0; i < indexes.Length; i++) 
     { 
      indexes[i] = i; 
     } 
    } 

    private static void SetIndexes(int[] indexes, int lastIndex, int count) 
    { 
     indexes[lastIndex]++; 
     if (lastIndex > 0 && indexes[lastIndex] == count) 
     { 
      SetIndexes(indexes, lastIndex - 1, count - 1); 
      indexes[lastIndex] = indexes[lastIndex - 1] + 1; 
     } 
    } 

    private static List<T> TakeAt<T>(int[] indexes, IEnumerable<T> list) 
    { 
     List<T> selected = new List<T>(); 
     for (int i = 0; i < indexes.Length; i++) 
     { 
      selected.Add(list.ElementAt(indexes[i])); 
     } 
     return selected; 
    } 

    private static bool AllPlacesChecked(int[] indexes, int places) 
    { 
     for (int i = indexes.Length - 1; i >= 0; i--) 
     { 
      if (indexes[i] != places) 
       return false; 
      places--; 
     } 
     return true; 
    } 

    public static IEnumerable<List<T>> GetDifferentCombinations<T>(this IEnumerable<T> collection, int count) 
    { 
     int[] indexes = new int[count]; 
     int listCount = collection.Count(); 
     if (count > listCount) 
      throw new InvalidOperationException($"{nameof(count)} is greater than the collection elements."); 
     InitIndexes(indexes); 
     do 
     { 
      var selected = TakeAt(indexes, collection); 
      yield return selected; 
      SetIndexes(indexes, indexes.Length - 1, listCount); 
     } 
     while (!AllPlacesChecked(indexes, listCount)); 

    } 
}