using System;
using System.Collections.Generic;
using System.Linq;

namespace AioNet.Linq
{
    public static class ExtendedLinq
    {
        public static IEnumerable<IEnumerable<T>> Combinations<T>(
            this IEnumerable<T> source,
            int subsequenceLength
        )
        {
            return source.Combinations<T>(subsequenceLength, Enumerable.Empty<T>());
        }

        private static IEnumerable<IEnumerable<T>> Combinations<T>(
            this IEnumerable<T> source,
            int subsequenceLength,
            IEnumerable<T> build
        )
        {
            if (build.Count() == subsequenceLength)
            {
                return new IEnumerable<T>[] { build };
            }

            if (!source.Any())
            {
                return Enumerable.Empty<IEnumerable<T>>();
            }

            IEnumerable<T> rest = source.Skip(1);

            IEnumerable<IEnumerable<T>> combinationsSkipping = rest.Combinations(
                subsequenceLength,
                build
            );
            IEnumerable<IEnumerable<T>> combinationsTaking = rest.Combinations(
                subsequenceLength,
                build.Append(source.First())
            );
            return combinationsTaking.Concat(combinationsSkipping);
        }
    }
}