使用多态方法生成排列

Question

说明：

Please write a piece of code that takes as an input a list in which each element is another list containing an unknown type and which returns a list of all possible lists that can be obtained by taking one element from each of the input lists.

For example:

[[1, 2], [3, 4]], should return: [[1, 3], [1, 4], [2, 3], [2, 4]].

[['1'], ['2'], ['3', '4' ]], should return [['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();
}

如何使用 returns 通用列表的多态方法使其工作？

Answer 1

我能想到的是他们并没有试图在列表中混合不同的类型（就像你实现的那样），所有列表的类型都是相同的，他们希望你写一个通用的 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();
}

与您的相比，此通用实现具有类型安全的优势，它确保您不会混合不同的对象类型。

Answer 2

Please write a piece of code that takes as an input a list in which each element is another list containing an unknown type and which returns a list of all possible lists that can be obtained by taking one element from each of the input lists.

我会要求澄清，比如 "You mean a generic method then?"

说到多态性，他们很可能只能编写一个方法并从任意类型调用它，例如：

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。

使用多态方法生成排列

Generate permutations using polymorphic method

c#

polymorphism

permutation