Come ottenere tutte le combinazioni di più elenchi <int>

Question

Differisce dalla soluzione zuccherata sopra in quanto una voce di elenco può apparire solo una volta per ogni riga.

Questo è per un sistema di prenotazione per la mia spa. Diversi dipendenti possono eseguire trattamenti diversi.

Ho un List<List<int>>. Questi sono terapisti che possono eseguire il trattamento prenotato.

Ogni lista (prenotazione) contengono un numero di interi come questo (questi sono i terapeuti che possono eseguire la prenotazione):

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

mi piacerebbe vedere tutte le possibili combinazioni in cui il numero può apparire solo in un posto. Per l'elenco di sopra dei due possibili ombinations sarebbero:

6,2,1,3 o 3,6,1,2

Questo è per la prima combinazione:

• Booking 1 : terapista 6
• Booking 2: terapista 2
• Booking 3: 1 terapista
• Booking 4: 3 terapista

Spero che ciò renda la domanda un po 'più chiara.

Answer 1

Questa soluzione è tutt'altro che efficiente:

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

Sembra che questo può essere risolto in modo più efficiente con la programmazione dinamica, ma è stato un po 'da quando ho preso il corso in questione.

Answer 2

risolvere con la ricorsione:

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

uscita:

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

Answer 3

Un modo semplice per guardare a questo problema sarebbe quello di scegliere tra tutte le combinazioni della lista di valori, in cui ogni valore nel la combinazione è unica.

Prima capire quali sono tutte le combinazioni di valori.

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

Quindi è necessario un modo per determinare se tutti i valori sono univoci. Un modo semplice per capirlo sarebbe quello di verificare se il conteggio di valori distinti equivale al conteggio di tutti i valori.

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

Una volta che hai tutto questo, metti tutto insieme.

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