用所有组合填充数组

本文关键字：填充 数组 组合 | 更新日期: 2023-09-27 18:02:17

给定一个枚举，我想知道如何填充一个锯齿数组，以便每个内部数组包含枚举值的组合(枚举中有7个值，内部数组中有6个槽，允许重复)，外部数组包含每个可能的组合(不是排列;红红红红橙和红红红红红橙红是同一个元素)。

多维数组也可以，尽管锯齿数组似乎更适用于现实世界的问题。我只是不知道如何编写填充它的循环。

语言是c#。我希望以一种从"最高"到"最低"值排序结果的方式填充它(从Red Red Red Red Red Red Red开始，然后是Red Red Red Red Red Orange，等等)。这是enum:

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

用所有组合填充数组

您可以使用简单的递归函数来实现它的可伸缩性。它接收要组合的项目数组，要从数组中选择的项目数量以及要从数组中选择项目的起始索引(默认为0)。它递归地在每个允许的起始位置选择第一个项目，并将所有其他元素的组合附加到项目数组的右侧。

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

它在0.44 ms内生成预期的924个组合，其中重复7个元素中的6个。这可能不是最好的性能，而且它使用的内存比可能的要多，但它的实现非常简单，并且对于这样数量的元素来说足够有效。

我发现这个问题很有趣，并继续研究解决方案…给你……

像这样使用代码…

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

按预期产生924个结果，并且不做任何不必要的计算或复制。以下是实际的方法。

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

享受吧!

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

如果你想生成任意长度的组合，那么你需要更复杂的东西。

编辑:您可以通过在每个from后面添加where子句来修复它:

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();
相关文章：