generare permutazioni usando il metodo polimorfico

Question

Le istruzioni:

Si prega di scrivere un pezzo di codice che prende come input una lista in cui ogni elemento è un altro elenco contenente un tipo sconosciuto, e che restituisce un elenco di tutti i liste possibili che possono essere ottenute prendendo un elemento da ciascuno degli elenchi di input.

Ad esempio:

[[1, 2], [3, 4]], dovrebbe restituire: [[1, 3], [1, 4], [2, 3], [2, 4]].

[['1'], ['2'], ['3', '4']], dovrebbe restituire [['1', '2', '3'], ['1', '2', '4']].

Il mio codice:

public static void Main(string[] args) 
{ 
    //Create a list of lists of objects. 
     var collections = new List<List<object>>(); 
     collections.Add(new List<object> { 1, 5, 3 }); 
     collections.Add(new List<object> { 7, 9 }); 
     collections.Add(new List<object> { "a", "b" }); 

    //Get all the possible permutations 
     var combinations = GetPermutations(collections); 

    //Loop through the results and display them in console 
     foreach (var result in combinations) 
     { 
      result.ForEach(item => Console.Write(item + " ")); 
      Console.WriteLine(); 
     } 

     Console.WriteLine("Press any key to exit."); 
     Console.ReadKey(); 
} 

private static List<List<object>> GetPermutations(List<List<object>> collections) 
{ 
     List<List<object>> permutations = new List<List<object>>(); 

     //Check if the input list has any data, else return the empty list. 
     if (collections.Count <= 0) 
      return permutations; 

     //Add the values of the first set to the empty List<List<object>> 
     //permutations list 
     foreach (var value in collections[0]) 
      permutations.Add(new List<object> { value }); 


     /* Skip the first set of List<List<object>> collections as it was 
     * already added to the permutations list, and loop through the 
     * remaining sets. For each set, call the AppendValues function 
     * to append each value in the set to the permuations list. 
     * */ 
     foreach (var set in collections.Skip(1)) 
      permutations = AppendNewValues(permutations, set); 

     return permutations; 
} 

private static List<List<object>> AppendNewValues(List<List<object>> permutations, List<object> set) 
{ 
     //Loop through the values in the set and append them to each of the 
     //list of permutations calculated so far. 
     var newCombinations = from additional in set 
           from value in permutations 
           select new List<object>(value) { additional }; 

     return newCombinations.ToList(); 
} 

Come potrei farlo funzionare con il metodo polimorfico che restituisce un elenco generico?

Answer 1

Si prega di scrivere un pezzo di codice che prende come input una lista in cui ogni elemento è un altro elenco contenente un tipo sconosciuto, e che restituisce un elenco di tutti i possibili liste che possono essere ottenuti prendendo un elemento da ciascuna delle gli elenchi di input.

Avrei chiesto chiarimenti, qualcosa come "Vuoi dire un metodo generico allora?"

Parlando di polimorfismo, furono probabilmente poter scrivere solo un metodo e lo chiamano formare qualsiasi tipo arbitrario, qualcosa di simile:

public static IList<IList<T>> GetPermutations<T>(IList<IList<T>> inputLists) { 
    if (inputLists.Count < 2) { 
     // special case. 
    } 

    return _permutationHelper(0, inputLists); 
} 

private static IList<IList<T>> _permutationHelper<T>(int i, IList<IList<T>> inputLists) { 
    IList<IList<T>> returnValue = new List<IList<T>>(); 
    if (i == inputLists.Count) { 
     returnValue.Add(new List<T>()); 
    } else { 
     foreach (var t in inputLists[i]) { 
      foreach (var list in _permutationHelper(i + 1, inputLists)) { 
       list.Add(t); 
       returnValue.Add(list); 
      } 
     } 
    } 

    return returnValue; 
} 

E 'vero che l'implementazione permetterebbe tipi arbitrari in fase di esecuzione , ma perde la sicurezza del tipo. Dato che si tratta di un'implementazione in C#, digitare sicurezza come requisito è un'ipotesi sicura, ma non fa male nemmeno chiedere.

Un'altra cosa di nota: avrebbero potuto semplicemente dire che stavano cercando lo Cartesian product degli elenchi dati.

Answer 2

Tutto quello che riesco a pensare è che non stavano provando a mescolare diversi tipi nelle liste (come hai implementato), i tipi di tutte le liste sarebbero gli stessi e volevano che scrivessi una Classe generica che gestisse il problema per i diversi tipi di liste, con conseguente qualcosa di simile:

static void Main(string[] args) 
{ 
    var intCollections = new List<List<int>>(); 
    intCollections.Add(new List<int> { 1, 5, 3 }); 
    intCollections.Add(new List<int> { 7, 9 }); 

    var stringCollections = new List<List<String>>(); 
    stringCollections.Add(new List<String> { "a", "b" }); 
    stringCollections.Add(new List<String> { "c","d", "e" }); 
    stringCollections.Add(new List<String> { "g", "f" }); 

    //here you would have the "polymorphism", the same signature for different Lists types 

    var intCombinations = GetPermutations(intCollections); 
    var stringCombinations = GetPermutations(stringCollections); 

    foreach (var result in intCombinations) 
    { 
     result.ForEach(item => Console.Write(item + " ")); 
     Console.WriteLine(); 
    } 

    Console.WriteLine(); 

    foreach (var result in stringCombinations) 
    { 
     result.ForEach(item => Console.Write(item + " ")); 
     Console.WriteLine(); 
    } 

    Console.WriteLine("Press any key to exit."); 
    Console.ReadKey(); 
} 

//This would be your generic implementation, basically changing from object to T and adding <T> after method 

private static List<List<T>> GetPermutations<T>(List<List<T>> collections) 
{ 
    List<List<T>> permutations = new List<List<T>>(); 

    //Check if the input list has any data, else return the empty list. 
    if (collections.Count <= 0) 
     return permutations; 

    //Add the values of the first set to the empty List<List<object>> 
    //permutations list 
    foreach (var value in collections[0]) 
     permutations.Add(new List<T> { value }); 


    /* Skip the first set of List<List<object>> collections as it was 
     * already added to the permutations list, and loop through the 
     * remaining sets. For each set, call the AppendValues function 
     * to append each value in the set to the permuations list. 
     * */ 
    foreach (var set in collections.Skip(1)) 
     permutations = AppendNewValues(permutations, set); 

    return permutations; 
} 

private static List<List<T>> AppendNewValues<T>(List<List<T>> permutations, List<T> set) 
{ 
    //Loop through the values in the set and append them to each of the 
    //list of permutations calculated so far. 
    var newCombinations = from additional in set 
          from value in permutations 
          select new List<T>(value) { additional }; 

    return newCombinations.ToList(); 
} 

questa generica implementazione, il confronto alla tua, hanno il vantaggio di tipo di sicurezza, rende sicuri di non mescolare diversi tipi di oggetto.