Populating an array with all combinations

Question

Given an enum, I was wondering how to populate a jagged array so that each inner array contains a combination of the enum values (7 values in the enum, 6 slots in the inner arrays, repeats allowed), and the outer array contains each possible combination (not permutation; Red Red Red Red Red Orange and Red Red Red Red Orange Red are the same element).

A multi-dimensional array would also work, though a jagged array would seem more applicable given the real-world problem. I'm just having trouble figuring out how the loop to populate it would be written.

The language is C#. I am hoping populate it in a way that sorts the results in order from "highest" to "lowest" value, (starting with Red Red Red Red Red Red, then Red Red Red Red Red Orange, etc.). This is the enum:

public enum OrderedColors
{
    Colorless,
    Purple,
    Blue,
    Green,
    Yellow,
    Orange,
    Red
}

Answer 1

You can do it with simple recursive function to make it scalable. It receives array of items to combine, number of items to select from array and start index in array where to seleft items from (default to 0). It recursifely selects first item at every allowed starting position and attaches all combinations of further elements to the right in the items array.

public static IEnumerable<T[]> BuildCombinations<T>(T[] items, int itemsCountInCombination, int startIndex = 0)
{
    if (itemsCountInCombination == 0)
    {
        yield return new T[0];
        yield break;
    }
    for (int i = startIndex; i < items.Length; i++)
    {
        foreach (var combination in BuildCombinations(items, itemsCountInCombination - 1, i))
        {
            var c = new T[itemsCountInCombination];
            c[0] = items[i];
            Array.Copy(combination, 0, c, 1, combination.Length);
            yield return c;
        }
    }
}


private static void Main(string[] args)
{
    foreach (var c in BuildCombinations(Enum.GetValues(typeof (OrderedColors)).Cast<OrderedColors>().Reverse().ToArray(), 6))
    {
        foreach (var color in c)
        {
            Console.Write(color);
            Console.Write(" ");
        }
        Console.WriteLine();
    }
}

It generates the expected 924 combinations with repetition of 6 elements out of 7 in 0,44ms. It's probably not the best possible performance and it uses more memory than possible, but it's very simple implementation and efficient enough for such number of elements.

Answer 2

I found this question interesting and continued working on a solution... here you go...

Use the code like this...

    var example = new[] { 
        OrderedColors.Red, OrderedColors.Orange, OrderedColors.Yellow, 
        OrderedColors.Green, OrderedColors.Blue, OrderedColors.Purple, 
        OrderedColors.Colorless };
    var combinations = example.CombinationsWithRepetition(6);

Which yields 924 results as expected and doesn't do any unecessary calculations or copying. Below are the actual methods.

    public static IEnumerable<IList<T>> CombinationsWithRepetition<T>
        (this IEnumerable<T> input, int take) where T : new()
    {
        var items = input.ToList();
        return CombinationsWithRepetition(items, null, take, 0, 0);
    }

    private static IEnumerable<IList<T>> CombinationsWithRepetition<T>
        (List<T> allItems, IList<T> thisSequence, int maxLength, 
        int currentLength, int currentIndex)
    {
        if (maxLength == 0)
            yield return new List<T>();
        for (var index = currentIndex; index < allItems.Count; index++)
        {
            var nextSequence = thisSequence == null ? new List<T>() : 
                  thisSequence.ToList();
            nextSequence.Add(allItems[index]);
            if (currentLength + 1 == maxLength)
            {
                yield return nextSequence;
            }
            else
            {
                foreach (var sequence in CombinationsWithRepetition(allItems, 
                   nextSequence, maxLength, currentLength + 1, index))
                {
                    yield return sequence;
                }
            }
        }
    }

Enjoy! It was fun writing it.

Answer 3

using LINQ:

OrderedColors[] colors = (OrderedColors[])Enum.GetValues(typeof(OrderedColors));

OrderedColors[][] matrix = (
    from a in colors
    from b in colors
    from c in colors
    from d in colors
    from e in colors
    from f in colors
    select new [] {a,b,c,d,e,f}
).ToArray();

If you want to make something that can generate combinations of any length, than you need something more complicated.

Edit: you can fix it by adding a where clause after each from:

OrderedColors[][] matrix = (
    from a in colors
    from b in colors
    where a<=b
    from c in colors
    where b<=c
    from d in colors
    where c<=d
    from e in colors
    where d<=e
    from f in colors
    where e<=f
    select new [] {a,b,c,d,e,f}
).ToArray();