Minutes from Algprog meeting of 20090424.
Presenter : Sharon Curtis
Sharon presented a solution to the maximum-density segment problem with decreasing right-skew partition (DRSP).
Density is defined as the total area of a sequence of items over the total width. In a DRSP, the density of each segment must be strictly decreasing and each segment must be right-skew (defined below)
forall u,v st. y = u++v => density u <= density v
The four ways that computes the unique DRSP is
drsp :: [Item] -> Item
drsp x = leftMunch lhdp - longest highest-density prefix
- = leftMunch lrsp -- longest right-Skew prefix
- = rightMunch llds
- = rightMunch lrss
leftMunch :: ([Item] -> [Item]) -> [Item] -> Item
leftMunch m  = 
leftMunch m x = y : leftMunch (drop (#y) x)
- where y = m x
Consider the maximum-density segment with a minimum length l.
The solution is to start with a suffix (window) of the sequence and take away the first l elements. The rest of the suffix is DRSPed. It is then checked segment by segment to append to the first l elements.
After this step, the remaining window (first l element + the chosen segments) is shifted leftwards by consing one element to the left. As a result, the first l compulsory elements are also shifted leftward and the DRSP of the remaining list is updated with one more element to the left.
This update is easy given the following property
tail (drsp (x:xs)) is a suffix of drsp xs
To implement this update, the sequence is represented as a tree.
DTree a = Node a [DTree a]
makeDTree (i,is) = Node i (map makeDTree (drsp is))
Ralf's comment here:
Density does not play a part here. It is all about partition properties,
which is orthogonal and more general.
This algorithm can be generalized with maximum-density segment with both a minimum length and a maximum length.
In general, it is needed to split a tree. It is again down to reDRSP it with a suffix dropped.
Jeremy and Geraint's proof of
density x <= density y and rightSkew x and rightSkew y implies rightSkew (x++y)
density x1 <= density (x1++x2++y) <= density (x2++y)