C#递归yield return不返回任何东西

问题描述 投票:0回答:1

这个问题可能在其他地方问过,但我找不到我的问题的解决方案。这个问题不是特定的语言,同样的问题在python中也可以问。任务是用算法生成一个字符串列表,如 Enumerable.Range但字符不仅限于1、2、3......,还可以是任何字符序列。最简单的例子是

TestCase 1输入:输入。

baseChars: ['a','b'], 所需字符串长度:2。

输出:['aa','ab','ba','bb']

['aa','ab','ba','bb']

测试案例2:

baseChars: ['a','b'] 所需字符串长度:1

输出:['a','b']

['a','b']

该功能运行良好。

    static IList<string> baseChars = new List<string>() { "0", "1", "2", "3" };
    static void CharsRange1(string prefix, int pos)
    {
        if (pos == 1)
        {
            foreach (string s in baseChars)
            {
                Console.WriteLine(prefix + s);
            }
        }
        else
        {
            foreach (string s in baseChars)
            {
                CharsRange1(prefix + s, pos - 1);
            }
        }
    }

预期和实际输出(为了节省空间,用逗号代替了新行): 000, 001, 002, 003, 010, 011, 012, 013, 020, 021, 022, 023, 030, 031, 032, 033, 100, 100:

000, 001, 002, 003, 010, 011, 012, 013, 020, 021, 022, 023, 030, 031, 032, 033, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 123, 130, 131, 132, 133, 200, 201, 202, 203, 210, 211, 212, 213, 220, 221, 222, 223, 230, 231, 232, 233, 300, 301, 302, 303, 310, 311, 312, 313, 320, 321, 322, 323, 330, 331, 332, 333

问题是把这个函数封装为一个库,所以返回类型应该是 IEnumerable<string>所以即使输入量很大,内存也不会爆炸,但我的代码 无以复加:

    static IEnumerable<string> CharsRange2(string prefix, int pos)
    {
        if (pos == 1)
        {
            foreach (string s in baseChars)
            {
                yield return prefix + s;
            }
        }
        else
        {
            foreach (string s in baseChars)
            {
                // here if i yield return then won't compile
                // i thought at the end of recursive loop it will return 
                CharsRange2(prefix + s, pos - 1);
            }
        }
    }

主。

    static void Main(string[] args)
    {
        //CharsRange1("", 3);//working
        foreach (string s in CharsRange2("", 3))
        {
            Console.WriteLine(s);//nothing
        }
        Console.WriteLine("end");
        Console.ReadKey();
    }

谁能帮帮我?我把我的代码放到了 github. 另外appreicated,如果你能改变我的实现非递归,但保持函数返回类型。

c# algorithm recursion permutation yield
1个回答
4
投票

方案1,从递归调用中产生每个值。

    foreach (string s in baseChars)
        foreach (var r in CharsRange2(prefix + s, pos - 1))
            yield return r;

方案2,重用现有的 IEnumerable 类型内置到框架中,以完全避免yield return。

    if (pos == 1)
        return baseChars.Select(s => prefix + s);
    else
        return baseChars.SelectMany(s => CharsRange2(prefix + s, pos - 1));

方案3,使用嵌套循环代替递归方法,留给读者练习。


2
投票

正如指出的调用 CharsRange2(prefix + s, pos - 1); 没有被使用。您需要将 foreachyield 每个结果。

这里有一个替代方案,它更多的是基于以下理念 Enumerable.Range.

从一个通用的换基器开始。

public static IEnumerable<int> ToBase(this int x, int b)
{
    IEnumerable<int> ToBaseReverse()
    {
        if (x == 0)
        {
            yield return 0;
            yield break;
        }
        int z = x;
        while (z > 0)
        {
            yield return z % b;
            z = z / b;
        }
    }

    return ToBaseReverse().Reverse();
}

现在添加一个方法来将其转换为一组特定的数字。

public static string ToBase(this int number, string digits) =>
    String.Concat(number.ToBase(digits.Length).Select(x => digits[x]));

可以像这样使用:

string result = 45.ToBase("0X2Y");
Console.WriteLine(result);

这样就可以得到:

2YX

现在,写下这样的文字是很简单的 Enumerable.Range(0, 10).Select(n => n.ToBase("0X2Y")).

由此可得。

0, X, 2, Y, X0, XX, X2, XY, 20, 2X。

这对所有非零的数字进行正确的计数,除了零本身,不显示前导零。

© www.soinside.com 2019 - 2024. All rights reserved.