c# - 与重复的组合 C#

Question

我需要有关重复组合的帮助。在网上搜索过，虽然我找到了一些例子，但我不能完全理解它们。我的目标很简单，一个函数 (CombinationsWithRepetiion) 接收包含项目(在本例中为整数值)和长度(代表每个组合的长度)的列表，并返回包含结果的列表。

    List<int> input = new List<int>() {1, 2, 3}
    CombinationsWithRepetition(input, length);

结果:

长度 = 1: 1, 2, 3

长度 = 2: 11,12,13,21,22,23,31,32,33

长度 = 3: 111,112 ....

我希望有人能帮助我并提前谢谢你!

Answer 1

递归

好的，

这是 C# 版本 - 我将带您完成

static IEnumerable<String> CombinationsWithRepetition(IEnumerable<int> input, int length)
{
    if (length <= 0)
        yield return "";
    else
    {
        foreach(var i in input)
            foreach(var c in CombinationsWithRepetition(input, length-1))
                yield return i.ToString() + c;
    }
}

首先检查递归的边界情况(在本例中为 length <= 0 )——在本例中答案是空字符串(顺便说一句:我选择返回字符串，因为你没有说出你真正需要的——应该是易于更改)。

在任何其他情况下，您查看每个输入 i 并递归地采用下一个更小的组合并将它们插入在一起(使用字符串连接，因为我想要字符串)。

我希望你理解 IEnumerable/yield 的东西——如果不明白请在评论中说出来。

这是一个示例输出:

foreach (var c in CombinationsWithRepetition(new int[]{1,2,3}, 3))
    Console.WriteLine (c);
111
112
113
...
332
333

转换数字

下面使用了我在下面的评论中勾勒出的想法并且没有堆栈溢出异常的问题(递归可能用于大长度) - 这也假设字符串因为它们更容易使用(我可以做一个简单的 PadLeft简化事情)

static String Convert(string symbols, int number, int totalLen)
{
    var result = "";
    var len = symbols.Length;
    var nullSym = symbols [0];
    while (number > 0)
    {
        var index = number % len;
        number = number / len;
        result = symbols [index] + result;
    }
    return result.PadLeft (totalLen, nullSym);
}

static IEnumerable<String> CombinationsWithRepetition(string symbols, int len)
{
    for (var i = 0; i < Math.Pow(symbols.Length,len); i++)
        yield return Convert (symbols, i, len);
}