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

namespace Permutation
{
    public static class Extension
    {
        public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
        {
            if (source == null)
                throw new ArgumentNullException("source");

            return PermutationsImpl(source, Enumerable.Empty<T>());
        }

        private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, IEnumerable<T> prefix)
        {
            if (!source.Any())
                yield return prefix;

            foreach (var permutation in source.SelectMany(x => PermutationsImpl(source.Except(Yield(x)), prefix.Union(Yield(x)))))
            {
                yield return permutation;
            }
        }

        private static IEnumerable<T> Yield<T>(this T element)
        {
            yield return element;
        }
    }
}