I need a c# function to determine the combinations of n max integers. Thanks

Question

Unlike other examples that provide combinations of n for k values, I have an array of n and I need a combination of all values from 0 - n. For example:

If I have an array of 5,8,3,4,9 the function would return:

0,0,0,0,0 0,0,0,0,1 ... 1,1,1,1,1 1,1,1,1,2 ... 5,8,3,4,9

I can accomplish this using a process to find the combinations of a max of n for k values, but it provides too many combinations (many of these combinations are invalid that I have to throw out):

private static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> list, int length) where T : IComparable
        {
            if (length == 1) return list.Select(t => new T[] { t });
            return GetCombinations(list, length - 1)
                .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

0,0,0,0,0 0,0,0,0,1 ... 9,9,9,9,9

Answer 1

Here's an implementation that would work for numeric types:

public static IEnumerable<T[]> Combinations<T>(T[] values) where T: INumber<T>
{
    var current = new T[values.Length];

    do
    {
        yield return current.ToArray();
    }
    while (increment());

    bool increment()
    {
        for (int index = current.Length - 1; index >= 0; --index)
        {
            if (++current[index] <= values[index])
                return true;

            current[index] = default!;
        }

        return false;
    }
}

Test code:

public static void Main()
{
    var array = new [] { 5, 8, 3, 4, 9 };

    foreach (var combination in Combinations(array))
    {
        Console.WriteLine(string.Join(", ", combination));
    }
}

However, your test code is using IComparable - I can't see how that would work with non-numeric IComparable types such as string and DateTime.

For example, what would it mean for an input array of {"Tom", "Dick", "Harry"} ?