Safe Haskell	Safe-Inferred
Language	Haskell2010

ToyLib.DP

Description

Typical DP utilities

TODO: Refactor relaxMany variants.

Synopsis

constructFor :: (Unbox a, Unbox b) => a -> Vector b -> (Vector a -> b -> a) -> Vector a
relaxMany :: (HasCallStack, Vector v a, Vector v (Int, a), Vector v b) => (a -> a -> a) -> v a -> v b -> (b -> v (Int, a)) -> v a
irelaxMany :: (HasCallStack, Vector v a, Vector v (Int, a), Vector v b) => (a -> a -> a) -> v a -> v b -> (Int -> b -> v (Int, a)) -> v a
relaxMany' :: (Monoid m, Unbox m, Unbox a) => Vector m -> Vector a -> (a -> Vector (Int, m)) -> Vector m
pushBasedConstructN :: (HasCallStack, Vector v a, Vector v (Int, a)) => (a -> a -> a) -> v a -> (Int -> v a -> v (Int, a)) -> v a
pushBasedConstructIV :: (HasCallStack, Unindex i, Unbox a) => (a -> a -> a) -> IxUVector i a -> (IxUVector i a -> i -> Vector (i, a)) -> IxUVector i a
type Span = (Int, Int)
twoSplits :: Int -> Int -> Vector (Span, Span)
iwiSpansU :: Int -> Int -> Vector (Span, Span)
iwiSpansU' :: Int -> Int -> Vector (Span, Int, Span)
spanDP :: Unbox a => Int -> a -> (Int -> a) -> (IxVector (Int, Int) (Vector a) -> (Int, Int) -> a) -> IxVector (Int, Int) (Vector a)
tspDP :: Int -> IxUVector (Int, Int) Int -> Vector Int
ordPowerset :: Int -> Vector Int
lisOf :: HasCallStack => Vector Int -> Int
lisOf' :: HasCallStack => Vector Int -> Vector Int
lcsOf :: ByteString -> ByteString -> Int
lastCharOccurrences :: ByteString -> Vector (Vector Int)
lexPerms :: (Vector v a, Ord a) => v a -> Vector (v a)

Documentation

constructFor :: (Unbox a, Unbox b) => a -> Vector b -> (Vector a -> b -> a) -> Vector a #

Variant of constructN.

relaxMany :: (HasCallStack, Vector v a, Vector v (Int, a), Vector v b) => (a -> a -> a) -> v a -> v b -> (b -> v (Int, a)) -> v a #

accumulate variant with concatMap-like expander. Be wanrned that *the input is consumed in-place*. Run like relaxMany vec0 (U.force vec0) $ x -> .. if it needs to be cloned.

relaxMany !f !vec0 !input !expander ~ G.accumulate f vec0 $ G.concatMap expander input

irelaxMany :: (HasCallStack, Vector v a, Vector v (Int, a), Vector v b) => (a -> a -> a) -> v a -> v b -> (Int -> b -> v (Int, a)) -> v a #

relaxMany with index input. Be wanrned that *the input is consumed in-place*. Run like relaxMany vec0 (U.force vec0) $ x -> .. if it needs to be cloned.

relaxMany' :: (Monoid m, Unbox m, Unbox a) => Vector m -> Vector a -> (a -> Vector (Int, m)) -> Vector m #

Monoid variant of relaxMany

pushBasedConstructN :: (HasCallStack, Vector v a, Vector v (Int, a)) => (a -> a -> a) -> v a -> (Int -> v a -> v (Int, a)) -> v a #

pushBasedConstructIV :: (HasCallStack, Unindex i, Unbox a) => (a -> a -> a) -> IxUVector i a -> (IxUVector i a -> i -> Vector (i, a)) -> IxUVector i a #

type Span = (Int, Int) #

$[l, r]$ span.

twoSplits :: Int -> Int -> Vector (Span, Span) #

Returns non-empty splits of a Span. >>> twoSplits 3 6 [((3,3),(4,6)),((3,4),(5,6)),((3,5),(6,6))]

iwiSpansU :: Int -> Int -> Vector (Span, Span) #

Returns two nullable splits of a span. >>> iwiSpansU 3 6 [((3,2),(4,6)),((3,3),(5,6)),((3,4),(6,6)),((3,5),(7,6))]

iwiSpansU' :: Int -> Int -> Vector (Span, Int, Span) #

Returns two nullables splits and a non-null mid point of a span.

>>> iwiSpansU' 3 6
[((3,2),3,(4,6)),((3,3),4,(5,6)),((3,4),5,(6,6)),((3,5),6,(7,6))]

Be sure to exclude the l and r points on three-point merge: iwiSpansU' (l + 1) (r - 1).

spanDP :: Unbox a => Int -> a -> (Int -> a) -> (IxVector (Int, Int) (Vector a) -> (Int, Int) -> a) -> IxVector (Int, Int) (Vector a) #

$O(N^3)$ Span-based DP with preset index patterns.

REMARK: sofar is accessed as @sofar ! (len, l)@@.

tspDP :: Int -> IxUVector (Int, Int) Int -> Vector Int #

Typical set-based DP (traveling salesman problem).

Typical problems

ABC 317 C - Remembering the Days

ordPowerset :: Int -> Vector Int #

Powerset with the lsb on, mainly for partitioning DP.

lisOf :: HasCallStack => Vector Int -> Int #

Longest increasing subsequence. **The input must be compressed**.

lisOf' :: HasCallStack => Vector Int -> Vector Int #

Longest increasing subsequence with path restoration. **The input must be compressed**.

lcsOf :: ByteString -> ByteString -> Int #

Longest common sequence.

lastCharOccurrences :: ByteString -> Vector (Vector Int) #

$O(W N) (W = 26)$ Returns a vector. vec V.! c U.! i indicates the last occurrence index of c (i and the returning index is 1-based). This is for subsequence DP.

NOTE: Input is limited to lower case characters.
NOTE: If character at i1 is c and want to know the last c, use i0 to get it.

lexPerms :: (Vector v a, Ord a) => v a -> Vector (v a) #