Generate permutations of an array of arrays

permutations_of_arrays.cs

// Get permutations of an array of arrays
// Adapted from: https://www.geeksforgeeks.org/combinations-from-n-arrays-picking-one-element-from-each-array/
public static IEnumerable<List<T>> PermutationsOfArrays<T>(IList<List<T>> arr)
{
    // Number of arrays
    int n = arr.Count();

    // Keep track of next element in each of the n arrays
    int[] indices = new int[n];

    List<List<T>> results = new List<List<T>>();

    while (true)
    {
        // Build current combination
        List<T> result = new List<T>();
        for (int i = 0; i < n; i++)
        {
            result.Add(arr[i][indices[i]]);
        }
        
        // Yield the result
        yield return result;

        // Find the rightmost array that has more elements left after the current element in that array
        int next = n - 1;
        while (next >= 0 && (indices[next] + 1 >= arr[next].Count))
        {
            next--;
        }

        // No such array is found so no more combinations left
        if (next < 0)
        {
            yield break;
        }

        // If found move to next element in that array
        indices[next]++;

        // For all arrays to the right of this array current index again points to first element
        for (int i = next + 1; i < n; i++)
        {
            indices[i] = 0;
        }
    }
}

// Helper for outputting nested list
public static void OutputNestedList<T>(IEnumerable<IEnumerable<T>> list)
{
    foreach(var li in list)
    {
        Console.WriteLine("{" + string.Join(", ", li) + "}");
    }
}

// Example use
public void Main()
{
    List<List<int>> integers = new List<List<int>>(){
        new List<int>(){1, 2, 3},
        new List<int>(){4},
        new List<int>(){5, 6, 7}
    };
    
    Console.WriteLine("Integers: ");
    OutputNestedList(integers);
    Console.WriteLine("");

    IEnumerable<IEnumerable<int>> permutations = PermutationsOfArrays(integers);

    Console.WriteLine("Permutations: ");
    OutputNestedList(permutations);
    
    /*
    Integers: 
    {1, 2, 3}
    {4}
    {5, 6, 7}

    Permutations: 
    {1, 4, 5}
    {1, 4, 6}
    {1, 4, 7}
    {2, 4, 5}
    {2, 4, 6}
    {2, 4, 7}
    {3, 4, 5}
    {3, 4, 6}
    {3, 4, 7}
    */
}