Get all subsequences of a sequence

Question

I have an array and I need all possible subarrays (segments or subsequences) with the exception of the empty one. This is not a power set, since every subarray has only elements that were contiguous in the input array.

For example, for input new int[]{1,2,3}, the output would be:

 new int[]{
   new int[]{1},
   new int[]{1,2},
   new int[]{1,2,3},
   new int[]{2},
   new int[]{2,3},
   new int[]{3}
 }

Note that {1,3} is not there because i don't want all subsets (the power set), just all subsequences.

I would prefer a solution using a single LINQ statement.

https://stackoverflow.com/questions/19890781/creating-a-power-set-of-a-sequence - realized this is a probable dupe — jdphenix, May 08 '19 at 18:40
Can the people voting this down care to given an explanation as to why? — Diego, May 08 '19 at 18:40
I imagine it's because your question reads like "I have a requirement, and I'd like someone to write the code for me" — stuartd, May 08 '19 at 18:42
@jdphenix That question is to get a power set (all combinations). What I want is all subsequences. — Diego, May 08 '19 at 18:42
From your post: "I need the power set of the array" - did you mean to write a different question? — NetMage, May 08 '19 at 18:43
@NetMage I edited the title and body based on my understanding of the problem. — jdphenix, May 08 '19 at 18:43
@jdphenix The example isn't a power set, it doesn't include `{ 1, 3 }`. — NetMage, May 08 '19 at 18:44
It is always useful to put the proper C# types in questions. `{1,2,3}` is not a valid C# object. — NetMage, May 08 '19 at 18:51
Possible duplicate of [Creating a power set of a Sequence](https://stackoverflow.com/questions/19890781/creating-a-power-set-of-a-sequence) — Bushuev, May 08 '19 at 21:20

NetMage · Accepted Answer · 2019-05-08T19:38:33.400

Assuming your source is a List (if not, convert to a List) then you can do:

var srcl = src.ToList();
var ans = Enumerable.Range(0, srcl.Count).SelectMany(start => Enumerable.Range(1, srcl.Count-start).Select(count => srcl.GetRange(start, count)));

Using a natural ArraySegment extension:

public static class ArrayExt {
    public static IEnumerable<T> Segment<T>(this T[] src, int start, int count) => new ArraySegment<T>(src, start, count);
}

You can have this return an array of arrays:

var ans = Enumerable.Range(0, src.Length).SelectMany(start => Enumerable.Range(1, src.Length-start).Select(count => src.Segment(start, count).ToArray()));

But List is generally preferred.

score 0 · Answer 2 · answered May 13 '19 at 23:47

Although NetMage's solution is correct, I ended up writing my own extension method that uses Array.Copy for performance:

/// <summary>
/// Get all subsequences of the given sequence.
/// {1,2,3}=>{{1,2},{1,2,3},{2,3}}
/// </summary>
public static T[][] GetAllSubsequences<T>(this IEnumerable<T> collection)
{
    var list = (collection as T[]) ?? collection.ToArray();
    return list.SelectMany((x, i) => list.Skip(i).Select((z, j) =>
          {
              var arr = new T[j + 1];
              Array.Copy(list, i, arr, 0, j + 1);
              return arr;
          })).ToArray();
}

Is there really a performance issue with `GetRange`? Besides error checking, `List.GetRange` actually uses `Array.Copy` internally. — NetMage, May 17 '19 at 21:44

Get all subsequences of a sequence

2 Answers2