title: Sequences in Spark dataframe
body: <p>I have dataframe in Spark. Looks like this:</p>
  
  <pre><code>+-------+----------+-------+
  |  value|     group|     ts|
  +-------+----------+-------+
  |      A|         X|      1|
  |      B|         X|      2|
  |      B|         X|      3|
  |      D|         X|      4|
  |      E|         X|      5|
  |      A|         Y|      1|
  |      C|         Y|      2|
  +-------+----------+-------+
  </code></pre>
  
  <p>Endgoal: I'd like to find how many sequences <code>A-B-E</code> (a sequence is just a list of subsequent rows) there are. With the added constraint that subsequent parts of the sequence can be maximum <code>n</code> rows apart. Let's consider for this example that <code>n</code> is 2.</p>
  
  <p>Consider group <code>X</code>.
  In this case there is exactly 1 <code>D</code> between <code>B</code> and <code>E</code> (multiple consecutive <code>B</code>s are ignored). Which means <code>B</code> and <code>E</code> are 1 row apart and thus there is a sequence <code>A-B-E</code></p>
  
  <p>I have thought about using <code>collect_list()</code>, creating a string (like DNA) and using substring search with regex. But I was wondering if there's a more elegant distributed way, perhaps using window functions?</p>
  
  <p>Edit:</p>
  
  <p>Note that the provided dataframe is just an example. The real dataframe (and thus groups) can be arbitrary long.</p>