[xquery-talk] longest sequence of monotonically increasingintegers

[Michael Kay]

This is actually a grouping problem. 

A few months ago there was an interesting thread on xsl-list discussing a
(real) problem with building back-of-book indexes, where the grouping
problem was to turn any sequence of consecutive integers within a sorted
sequence into a group. So 

( 1945, 1951, 1952, 1953, 1961, 1962, 1998 )

would be turned into

<e page="1945"/>
<e from="1951" to="1953"/> 
<e page="1961" to="1962/>
<e page="1998"/>

It might be worth thinking of your problem as two subproblems: (a) form the
groups, and (b) find the size of the largest group. The interesting part is
(a), I'll assume (b) is easy.

David Carlisle (IIRC) devised an elegant XSLT solution to the grouping
problem along the lines:

<xsl:for-each-group select="$input" group-adjacent=". - position()">
    <xsl:choose>
    <xsl:when test="count(current-group())=1">
      <e page="{.}"/>
    <xsl:when>
    <xsl:otherwise>
      <e from="{current-group()[1]}" to="{current-group()[last()]"/>
    </xsl:otherwise>
    </xsl:choose>
</xsl:for-each-group> 

(In fact group-adjacent isn't really necessary here, it could equally be
group-by)

The XQuery analogy of this would be something like

let $keys := distinct-values(
  for $page at $i in $input return ($page - $i))
for $key in $keys
let $range := for $page at $i in $input 
              where ($page - $i) = $key)
              return $page 
return
  if (count($range)=1)
  then <e page="{$range[1]}"/>
  else <e from="{min($range)}" to="{max($range)}"/>

Of course recursive solutions like Peter's might also be appropriate (I note
he handles duplicates in the sequence, which I don't)

Michael Kay
http://www.saxonica.com/


> -----Original Message-----
> From: talk-bounces at xquery.com 
> [mailto:talk-bounces at xquery.com] On Behalf Of Peter Coppens
> Sent: 03 March 2006 08:25
> To: Howard Katz; talk at xquery.com
> Subject: RE: [xquery-talk] longest sequence of monotonically 
> increasingintegers
> 
> I am sure someone can come up with a more elegant solution, but I have
> the impression this one does the trick
> 
> declare function local:f
>   ($running as xs:integer,$max as xs:integer,$seq as xs:integer*) 
>     as xs:integer {
>   if($seq[1] + 1 eq $seq[2]) then
>     local:f($running + 1, $max, subsequence($seq,2))
>   else if($seq[1] eq $seq[2]) then
>     local:f($running, $max, subsequence($seq,2))
>   else if(exists(subsequence($seq,2))) then
>     local:f(1, max(($max,$running)),subsequence($seq,2))
>   else
>     max(($max,$running))
> };
> 
> local:f(1 ,1, ( 1945, 1951, 1952, 1952, 1953, 1961, 1962, 1998 ))
> 
> 
> Hope it helps,
> 
> Peter
> 
> > -----Original Message-----
> > From: talk-bounces at xquery.com [mailto:talk-bounces at xquery.com] On
> Behalf
> > Of Howard Katz
> > Sent: Friday, March 03, 2006 3:29 AM
> > To: talk at xquery.com
> > Subject: [xquery-talk] longest sequence of monotonically increasing
> > integers
> > 
> > Anybody have a nice method of finding the length of the longest
> > monotonically increasing subsequence in a sequence of integers? For
> > example
> > given
> > 
> >      ( 1945, 1951, 1952, 1952, 1953, 1961, 1962, 1998 )
> > 
> > I need to be able to derive "3" for the run ( 1951, 1952, 
> 1953 ). The
> > double
> > entry for "1952" can be ignored.
> > 
> > TIA,
> > Howard
> > 
> > _______________________________________________
> > talk at xquery.com
> > http://xquery.com/mailman/listinfo/talk
> 
> _______________________________________________
> talk at xquery.com
> http://xquery.com/mailman/listinfo/talk
>