Generate permutations using polymorphic method

Question

The instructions :

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']].

My code:

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

How could I make it work with polymorphic method that returns a generic list?

Answer 1

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.

I would have asked for clarification, something like "You mean a generic method then?"

In speaking of polymorphism, they were likely being able to write just one method and call it form any arbitrary type, something like:

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

It is true that your implementation would allow arbitrary types at run time, but it loses type safety. Given that it's an implementation in C#, type safety being a requirement is a safe guess - but it doesn't hurt to ask either.

Another thing of note - they could have just said they were looking for the Cartesian product of the given lists.

Answer 2

All I can think of is that they were not trying to mix different types in the lists(like you implemented), the types of all lists would be the same and they wanted you to write a Generic Class that would handle the problem for different types of lists, resulting in something like this:

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

This generic implementation, comparing to yours, have the advantage of type Safety, it makes sure you will not mix different object types.