Jak uzyskać wszystkie kombinacje kilku list? <int>

Question

Różni się od sugerowanego rozwiązania powyżej, że element listy może pojawić się tylko raz dla każdego wiersza.

Jest to system rezerwacji dla mojego spa. Różni pracownicy mogą wykonywać różne zabiegi.

Mam List<List<int>>. Są to terapeuci, którzy mogą wykonać zabieg, który jest zarezerwowany.

Każda lista (rezerwacja) zawierają szereg liczb tak (są to terapeuci, który może wykonać rezerwację):

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

chciałbym zobaczyć wszystkie możliwe kombinacje, w których liczba może się pojawić tylko w jedno miejsce. Na powyższej liście dwa możliwe ombinations byłoby:

6,2,1,3 lub 3,6,1,2

To dla pierwszej kombinacji:

• rezerwacja 1 : Terapeuta 6
• Rezerwacja 2: Terapeuta 2
• rezerwacji 3: Terapeuta 1
• rezerwacja 4: Terapeuta 3

Mam nadzieję, że to sprawia, że ​​pytanie jest trochę bardziej przejrzyste.

Answer 1

To rozwiązanie jest dalekie od wydajny:

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

Brzmi jak to można rozwiązać bardziej efektywnie z programowania dynamicznego, ale to było dawno wziąłem odpowiedni kurs.

Answer 2

rozwiązać przez rekurencję:

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

wyjściowa:

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

Answer 3

Prosty sposób, aby spojrzeć na ten problem byłoby wybierać spośród wszystkich kombinacji liście wartości, gdzie każda wartość w kombinacja jest wyjątkowa.

Najpierw sprawdź, jakie są wszystkie kombinacje wartości.

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

Następnie trzeba ustalić, czy wszystkie wartości są unikatowe. Prostym sposobem rozpoznania tego byłoby sprawdzenie, czy liczba odrębnych wartości jest równa liczbie wszystkich wartości.

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

Gdy wszystko już masz, połóż wszystko razem.

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