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?

There is a nice blog about [permutations by Eric Lippert](https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiS9afz1erLAhUDtRoKHS0KC7gQFgggMAA&url=http%3A%2F%2Fericlippert.com%2F2013%2F04%2F15%2Fproducing-permutations-part-one%2F&usg=AFQjCNELiYNC3091lbttaXec9OFgUqEAAw) — René Vogt, Mar 31 '16 at 10:03
My question doesn't seem to be on permutations, e.g., I'm not interested in `[B, A]`? — D.R., Mar 31 '16 at 10:04
@Yuval Izzchakov: please reopen my question, it is not a duplicate, thank you. — D.R., Mar 31 '16 at 10:05
Do you need to maintain order of objects in your permutations? Because unless you do, how is `[A,B]` different than `[B,A]`? — Yuval Itzchakov, Mar 31 '16 at 10:06
i think OP needs the output as he showed, he do not need all possible combinations — Ehsan Sajjad, Mar 31 '16 at 10:06
I'm not sure but I guess the O(n) requirement is met by Yuval Itzchakov's answer. — René Vogt, Mar 31 '16 at 10:14

Yuval Itzchakov · Accepted Answer · 2016-03-31T12:17:44.720

4

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;
        }
    }
}

edited Mar 31 '16 at 12:17

answered Mar 31 '16 at 10:10

Yuval Itzchakov

146,575
32
257
321

i like your solution :) +1 – Ehsan Sajjad Mar 31 '16 at 10:13
@EʜsᴀɴSᴀᴊᴊᴀᴅ Thanks :) – Yuval Itzchakov Mar 31 '16 at 10:13
``yield return`` will cause to create a new IEnumerable? – Ehsan Sajjad Mar 31 '16 at 10:19
No, he's simply receiving views of the data each time as he iterates. As I added to my answer, if he wants to create a separate enumerator for each permutation, he'll have to either return a new `List`, or yield return each item. – Yuval Itzchakov Mar 31 '16 at 10:20
so same instances of string are being used again and again right? – Ehsan Sajjad Mar 31 '16 at 10:22
Yes. Currently, as he's enumerating the same list is re-used over. If he needs this for printing purposes, this will do fine. – Yuval Itzchakov Mar 31 '16 at 10:23
makes sense, Thanks for clarifying – Ehsan Sajjad Mar 31 '16 at 10:24
Thank you, that looks very nice. My only concern is the naming. According to Wikipedia sub lists are not permutations of a list. So maybe `GetOrderedPermutations` is not the best name. I've opened a separate question discussing this topic: https://stackoverflow.com/questions/36331843/name-for-a-prefix-list-data-structure – D.R. Mar 31 '16 at 11:18
@D.R You're right. It's definitely not a permutation, it's rather a function: X -> P(X). I changed the name to something more suitable. – Yuval Itzchakov Mar 31 '16 at 12:18
By `P(X)` I mean the power set of `X`. – Yuval Itzchakov Mar 31 '16 at 12:24

score 0 · Answer 2 · answered Mar 31 '16 at 10:09

Yes you are right, your requirement is such a small subset of permutations that is has nothing to do with permutations anymore. So here my suggestion:

var result = Enumerable.Range(1, list.Count).
                Select(i => list.Take(i).ToList()).
                ToList();

score 0 · Answer 3 · answered Mar 31 '16 at 10:10

You could iterate over a range of the number of items in your list and select the sublist like so:

var list = new List<string> { "A", "B", "C", "D", "E"};

var query =
    from i in Enumerable.Range(1, list.Count)
    select list.Take(i);

Keep in mind that if your data is not in a List<T> Count might be expensive. Also keep in mind that this iterates over your data more than once.

Get an enumerable of all sub lists of an existing list

3 Answers3