Cách lấy tất cả các kết hợp của một số Danh sách <int>

Question

Khác với giải pháp sugested ở trên, mục danh sách chỉ có thể xuất hiện một lần cho mỗi hàng.

Đây là hệ thống đặt chỗ cho spa của tôi. Các nhân viên khác nhau có thể thực hiện các cách điều trị khác nhau.

Tôi có số List<List<int>>. Đây là những nhà trị liệu có thể thực hiện điều trị được đặt trước.

Mỗi danh sách (đặt phòng) có chứa một số nguyên như thế này (đây là những nhà trị liệu có thể thực hiện đặt phòng):

{1, 3, 6}, //Booking 1 
{1, 2, 6}, //Booking 2 
{1},  //Booking 3 
{2,3}  //Booking 4 

tôi muốn xem tất cả các kết hợp có thể có số chỉ có thể xuất hiện trong một nơi. Để xem danh sách phía trên hai ombinations có thể sẽ là:

6,2,1,3 hoặc 3,6,1,2

Đó là dành cho sự kết hợp đầu tiên:

• đăng ký trước 1 : trị liệu 6
• đăng ký trước 2: Trị Liệu 2
• đăng ký trước 3: Trị Liệu 1
• Đặt trước 4: Trị Liệu 3

Hy vọng điều này làm cho câu hỏi trở nên rõ ràng hơn một chút.

Answer 1

Giải pháp này còn lâu mới hiệu quả:

private static void Main() 
    { 
     List<List<int>> list = new List<List<int>> 
      { 
       new List<int>() {1, 3, 6}, //Booking 1 
       new List<int>() {1, 2, 6}, //Booking 2 
       new List<int>() {1}, //Booking 3 
       new List<int>() {2, 3} 
      }; 
     List<int[]> solutions = new List<int[]>(); 
     int[] solution = new int[list.Count]; 
     Solve(list, solutions, solution); 
    } 

    private static void Solve(List<List<int>> list, List<int[]> solutions, int[] solution) 
    { 
     if (solution.All(i => i != 0) && !solutions.Any(s => s.SequenceEqual(solution))) 
      solutions.Add(solution); 
     for (int i = 0; i < list.Count; i++) 
     { 
      if (solution[i] != 0) 
       continue; // a caller up the hierarchy set this index to be a number 
      for (int j = 0; j < list[i].Count; j++) 
      { 
       if (solution.Contains(list[i][j])) 
        continue; 
       var solutionCopy = solution.ToArray(); 
       solutionCopy[i] = list[i][j]; 
       Solve(list, solutions, solutionCopy); 
      } 
     } 
    } 

Có vẻ như điều này có thể được giải quyết một cách hiệu quả hơn với lập trình năng động, nhưng nó được một lúc kể từ khi tôi mất quá trình có liên quan.

Answer 2

Giải quyết bằng cách đệ quy:

static IEnumerable<List<int>> GetCombinations(IEnumerable<List<int>> lists, IEnumerable<int> selected) 
{ 
    if (lists.Any()) 
    { 
     var remainingLists = lists.Skip(1); 
     foreach (var item in lists.First().Where(x => !selected.Contains(x))) 
      foreach (var combo in GetCombinations(remainingLists, selected.Concat(new int[] { item }))) 
       yield return combo; 
    } 
    else 
    { 
     yield return selected.ToList(); 
    } 
} 

static void Main(string[] args) 
{ 
    List<List<int>> lists = new List<List<int>> 
    { 
     new List<int> { 1, 3, 6 }, 
     new List<int> { 1, 2, 6 }, 
     new List<int> { 1 }, 
     new List<int> { 2, 3 } 
    }; 

    var combos = GetCombinations(lists, new List<int>()).Distinct(); 

    foreach (var combo in combos) 
     Console.WriteLine("{ " + string.Join(", ", combo.Select(x => x.ToString())) + " }"); 

    return; 
} 

Output:

{ 3, 6, 1, 2 } 
{ 6, 2, 1, 3 } 

Answer 3

Một cách đơn giản để nhìn vào vấn đề này sẽ được chọn từ tất cả các kết hợp của danh sách các giá trị, nơi mỗi giá trị trong kết hợp là duy nhất.

Đầu tiên tìm hiểu xem tất cả các kết hợp của giá trị là gì.

public static IEnumerable<IList<T>> Combinations<T>(IEnumerable<IList<T>> collections) 
{ 
    if (collections.Count() == 1) 
    { 
     foreach (var item in collections.Single()) 
      yield return new List<T> { item }; 
    } 
    else if (collections.Count() > 1) 
    { 
     foreach (var item in collections.First()) 
     foreach (var tail in Combinations(collections.Skip(1))) 
      yield return new[] { item }.Concat(tail).ToList(); 
    } 
} 

Sau đó, bạn cần một cách để xác định xem tất cả các giá trị có phải là duy nhất hay không. Một cách đơn giản để tìm ra điều đó sẽ là kiểm tra xem số lượng các giá trị riêng biệt có bằng tổng số của tất cả các giá trị hay không.

public static bool AllUnique<T>(IEnumerable<T> collection) 
{ 
    return collection.Distinct().Count() == collection.Count(); 
} 

Khi bạn đã có tất cả, hãy tập hợp tất cả lại với nhau.

var collections = new[] 
{ 
    new List<int> { 1, 3, 6 }, 
    new List<int> { 1, 2, 6 }, 
    new List<int> { 1 }, 
    new List<int> { 2, 3 }, 
}; 
var results = 
    from combination in Combinations(collections) 
    where AllUnique(combination) 
    select combination; 
// results: 
// 3,6,1,2 
// 6,2,1,3