C# рекурсивный возврат yield ничего не возвращает - PullRequest
Новая
       67

C# рекурсивный возврат yield ничего не возвращает

0 голосов
/ 16 июня 2020

Проблема могла быть задана в другом месте, но я не могу найти решение своей проблемы. Проблема не в языке c, ту же проблему можно задать в python. Задача состоит в том, чтобы алгоритм сгенерировал список строк типа Enumerable.Range, но символы не ограничены только 1, 2, 3 ... но могут быть любой последовательностью символов. Самый простой пример:

TestCase 1 :
ввод:

baseChars: ['a', 'b'],
обязательно длина строки: 2

вывод:

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

TestCase 2 :

baseChars: ['a', 'b']
требуемая длина строки: 1

вывод:

['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, 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>, чтобы память не взорвалась накануне n для большого ввода. но мой код ничего не может вернуть : 

    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 . Также рекомендуется, если вы можете изменить мою реализацию на нерекурсивную, но сохранить возвращаемый тип функции.

Ответы [ 2 ]

4 голосов
/ 16 июня 2020

Вариант 1, получение каждого значения из рекурсивного вызова. 

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

Вариант 2, повторное использование существующих IEnumerable типов, встроенных в структуру, чтобы полностью избежать возврата yield; 

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

Вариант 3, использовать вложенные циклы вместо рекурсивного метода, оставлен в качестве упражнения для читателя.

2 голосов
/ 16 июня 2020

Как указано, вызов CharsRange2(prefix + s, pos - 1); не используется. Вам нужно вложить foreach и yield каждый результат.

Вот альтернатива, которая больше основана на идее 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();
}

Теперь добавьте метод для преобразования этого в определенный c набор цифр: 

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

Это правильно подсчитывается для всех ненулевых чисел, без отображение первых нулей, кроме самого нуля.

...