Get an enumerable of all sub lists of an existing list

Question

I have a List<T> and I want to obtain all possible sub lists, e.g.:

[A, B, C, D, E] => [[A], [A, B], [A, B, C], [A, B, C, D], [A, B, C, D, E]]

Is there an easy way to do obtain this new enumerable with LINQ to Objects?

EDIT 1: Note that I only want "prefix lists", not all possible permutations (i.e., the shown example result is already complete).

EDIT 2: Note that I want to maintain the order of the elements as well.

EDIT 3: Is there a way to obtain the enumerables in O(n) instead of O(n²), i.e., by iterating over the source only once instead of multiple times and returning some kind of view on the data instead of a new list each time?

Answer 1

A very naive extension method:

public static class Extensions
{
    public static IEnumerable<IEnumerable<T>> GetOrderedSubEnumerables<T>(
                                              this IEnumerable<T> collection)
    {
        var builder = new List<T>();
        foreach (var element in collection)
        {
            builder.Add(element);
            yield return builder;
        }
    }
}

Use:

void Main()
{
    var list = new List<string> { "A", "B", "C", "D", "E" };
    Console.WriteLine(list.GetOrderedSubEnumerables());
}

Result:

Note this will return views of your data as you iterate the collection. But eventually, if you need to consume each permutation separately, you'll need to copy each List<T> over before yielding it back. In that case, this should do it:

public static class Extensions
{
    public static IEnumerable<IEnumerable<T>> GetOrderedSubEnumerables<T>(
                                              this IEnumerable<T> collection)
    {
        var builder = new List<T>();
        foreach (var element in collection)
        {
            builder.Add(element);
            var local = new List<T>(builder);
            yield return local;
        }
    }
}