Генерация перестановок с использованием полиморфных методу

Question

Инструкции:

Пожалуйста, напишите кусок кода, который принимает в качестве входных данных список, в котором каждый элемент является другой список, содержащий неизвестный тип и который возвращает список всех возможные списки, которые могут быть получены путем принятия одного элемента из каждого входного списка.

Например:

[[1, 2], [3, 4]], должна возвращать: [[1, 3], [1, 4], [2, 3], [2, 4]].

[['1'], ['2'], ['3', '4']] должен возвращать [['1', '2', '3'], ['1', '2', '4']].

Мой код:

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

Как я мог заставить его работать с полиморфного метода, который возвращает общий список?

Answer 1

Пожалуйста, напишите фрагмент кода, который вводит в качестве списка список, в котором каждый элемент представляет собой другой список, содержащий неизвестный тип, и который возвращает список всех возможных списков, которые могут быть получены путем взятия одного элемента из каждого из входные списки.

Я бы попросил разъяснений, что-то вроде «Вы имеете в виду общий метод?»

Говоря о полиморфизма, они, вероятно, были в состоянии написать только один метод и называют его образуют произвольный тип, что-то вроде:

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

Это правда, что ваша реализация позволит произвольных типов во время выполнения , но он теряет безопасность типа. Учитывая, что это реализация на C#, безопасность типа, являющаяся требованием, является надежной догадкой - но это не помешает спросить.

Другое примечание - они могли бы просто сказать, что искали Cartesian product данных списков.

Answer 2

Все, о чем я могу думать, это то, что они не пытались смешивать разные типы в списках (например, вы реализовали), типы всех списков были бы одинаковыми, и они хотели, чтобы вы написали Generic Class, который обрабатывал бы проблема для различных типов списков, в результате чего-то вроде этого:

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

Эта общая реализация, по сравнению с вашим, имеют преимущество типа безопасности, это гарантирует, что вы не будете смешивать различные типы объектов.