Что не так с этим методом c#, использующим Linq? - PullRequest
Новая
       57

Что не так с этим методом c#, использующим Linq?

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

Я попытался написать метод, который, учитывая переменную int Enumerable и int (назовем ее n), он генерирует все подпоследовательности, сумма которых меньше n.

Вот как это происходит: 

public static IEnumerable<IEnumerable<int>> SubSWithSumSmallerThanN(this IEnumerable<int> intEnum, int n)
    {
        var numbers = intEnum.ToList();
        return Enumerable
            .Range(1, numbers.Count)
            .SelectMany(length => Enumerable.Range(0, numbers.Count - length + 1)
                                            .Select(x => numbers.TakeWhile(y => numbers.IndexOf(y) > x && numbers.IndexOf(y) < x + length)))
                                            .Where(x => x.Sum() <= n)
            .ToArray();
    }

В принципе, это не работает. Для простого примера, такого как 

{1, 5, 3, 8}, n = 7

, тогда как результат должен быть 

{{1}, {5}, {3}, {1, 5}}

, фактический результат таков: 

Expected: List<IEnumerable<Int32>> [[1], [5], [3], [1, 5]]
Actual:   IEnumerable`1[] []

Он генерирует в основном пустой IEnumerable . Как это исправить?

1 Ответ

1 голос
/ 18 июня 2020

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

public static IEnumerable<IEnumerable<int>> SubsequencesLessThen(IReadOnlyList<int> input, int limit)
{
    for (int i = 0; i < input.Count; i++)
    {
        int sum = 0;
        for (int j = i; j < input.Count; j++)
        {
            sum += input[j];
            if (sum >= limit)
                break;

            yield return input.Skip(i).Take(j - i + 1);
        }
    }
}

Ближайший эквивалент, который я мог придумать, используя только linq: 

public static IEnumerable<IEnumerable<int>> SubsequencesLessThen2(IReadOnlyList<int> input, int limit)
{
    return from i in Enumerable.Range(0, input.Count)
        from j in Enumerable.Range(i, input.Count - i)
        let elements = input.Skip(i).Take(j - i + 1)
        let sum = elements.Sum()
        where sum <= limit
        select elements;
}

Это довольно немного дороже: мы не останавливаемся, как только замечаем, что сумма превышает лимит, поэтому будет вычислено 1+5, затем 1+5+3, затем 1+5+3+8, 5+3 и так далее. Мы также каждый раз пересчитываем сумму, вместо того, чтобы сохранять промежуточную сумму.

...