Можно ли избавиться от рекурсии в моем расширении «Комбинации»? А может это вообще не нужно? - PullRequest
Новая
       24

Можно ли избавиться от рекурсии в моем расширении «Комбинации»? А может это вообще не нужно?

0 голосов
/ 13 января 2019

Я написал небольшой класс Extension для генерации комбинаций элементов (без повторов и перестановок). Я использую рекурсию и задаюсь вопросом, как от нее избавиться и нужна ли она вообще. Может ли быть так, что компилятор C # преобразует его в итерации, хотя (методы, похоже, не являются хвостовой рекурсией)? Вот этот класс: 

public static partial class Extensions
{
    /// <summary>
    /// Combines elements of all sizes starting from 1 and up to the number of elements.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="items">Elements to be combined.</param>
    /// <returns></returns>
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> items)
    {
        var i = 0;
        foreach (var item in items)
        {
            i++;
            yield return new[] { item };
            foreach (var sub in Combinations(items.Skip(i)))
                yield return new[] { item }.Concat(sub);
        }
    }

    /// <summary>
    /// Combines elements only of a given size.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="items">Elements to be combined.</param>
    /// <param name="size">Size of the combination.</param>
    /// <returns></returns>
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> items, int size)
    {
        int i = 0;
        foreach (var item in items)
        {
            i++;
            if (size == 1)
                yield return new T[] { item };
            else
            {
                foreach (var result in Combinations(items.Skip(i), size - 1))
                    yield return new T[] { item }.Concat(result);
            }
        }
    }

    /// <summary>
    /// Combines elements of sizes from a given min to a given max.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="items">Elements to be combined.</param>
    /// <param name="min">Min size of combination.</param>
    /// <param name="max">Max size of combination.</param>
    /// <returns></returns>
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> items, int min, int max)
    {
        int i = 0;
        foreach (var item in items)
        {
            i++;
            if (max == 1)
                yield return new T[] { item };
            else
            {
                if (min <= 1)
                    yield return new T[] { item };
                foreach (var result in Combinations(items.Skip(i), min - 1, max - 1))
                    yield return new T[] { item }.Concat(result);
            }
        }
    }
}
...