sym 0.4 → 0.4.1
raw patch · 5 files changed
+88/−10 lines, 5 files
Files
- Math/Sym.hs +17/−0
- Math/Sym/Internal.hs +33/−1
- Math/Sym/Stat.hs +14/−2
- sym.cabal +1/−1
- tests/Properties.hs +23/−6
Math/Sym.hs view
@@ -57,6 +57,10 @@ , rMaxima -- :: Perm a => a -> Set , rMinima -- :: Perm a => a -> Set + -- * Components and skew components+ , components+ , skewComponents+ -- * Simple permutations , simple -- :: Perm a => a -> Bool @@ -387,6 +391,19 @@ -- | The set of indices of right-to-left minima. rMinima :: Perm a => a -> Set rMinima = I.rMaxima . I.complement . toVector . st+++-- Components and skew components+---------------------------------++-- | The set of indices of components.+components :: Perm a => a -> Set+components = I.components . toVector . st++-- | The set of indices of skew components.+skewComponents :: Perm a => a -> Set+skewComponents = I.components . I.complement . toVector . st+ -- Simple permutations -- -------------------
Math/Sym/Internal.hs view
@@ -77,6 +77,7 @@ , rir -- right-most increasing run , rdr -- right-most decreasing run , comp -- components+ , scomp -- skew components , ep -- rank a la Elizalde & Pak , dim -- dimension , asc0 -- small ascents@@ -86,6 +87,9 @@ , lMaxima , rMaxima + -- * Components+ , components+ -- * Sorting operators , stackSort , bubbleSort@@ -471,6 +475,10 @@ comp :: Perm0 -> Int comp = stat c_comp +-- | The number of skew components. +scomp :: Perm0 -> Int+scomp = comp . complement+ -- | Rank as defined by Elizalde & Pak. ep :: Perm0 -> Int ep = stat c_ep@@ -487,10 +495,11 @@ des0 :: Perm0 -> Int des0 = stat c_des0 + -- Left-to-right maxima, etc -- ------------------------- --- | The list of indices of left-to-right maxima.+-- | The set of indices of left-to-right maxima. lMaxima :: Perm0 -> SV.Vector Int lMaxima w = runST $ do v <- MV.unsafeNew n@@ -508,10 +517,32 @@ else iter v (i-1) j m +-- | The set of indices of right-to-left maxima. rMaxima :: Perm0 -> SV.Vector Int rMaxima w = SV.reverse . SV.map (\x -> SV.length w - x - 1) . lMaxima $ reverse w +-- Components+-- ----------++-- | The set of indices of components.+components :: Perm0 -> SV.Vector Int+components w = runST $ do+ v <- MV.unsafeNew n+ k <- iter v n 0 (-1)+ SV.unsafeFreeze $ MV.unsafeSlice 0 k v+ where+ n = size w+ {-# INLINE iter #-}+ iter _ 0 _ _ = return 0+ iter v i j m = do+ let m' = max m $ (SV.!) w (n-i)+ if m' == n-i then do+ MV.unsafeWrite v j (n-i)+ (+1) `liftM` iter v (i-1) (j+1) m'+ else+ iter v (i-1) j m'+ -- Sorting operators -- ----------------- @@ -536,6 +567,7 @@ -- | One pass of bubble-sort. bubbleSort :: Perm0 -> Perm0 bubbleSort = sortop c_bubblesort+ -- Single point deletions -- ----------------------
Math/Sym/Stat.hs view
@@ -42,19 +42,21 @@ , rir -- right-most increasing run , rdr -- right-most decreasing run , comp -- components+ , scomp -- skew components , ep -- rank a la Elizalde & Pak , dim -- dimension , asc0 -- small ascents , des0 -- small descents+ , shad -- shadow ) where import Prelude hiding (head, last)-import Math.Sym (Perm, toVector, st)+import Math.Sym (Perm, toVector, st, shadow) import Math.Sym.Internal (Perm0) import qualified Math.Sym.Internal as I ( asc, des, exc, fp, cyc, inv, maj, comaj, peak, vall, dasc, ddes , lmin, lmax, rmin, rmax- , head, last, lir, ldr, rir, rdr, comp, ep, dim, asc0, des0+ , head, last, lir, ldr, rir, rdr, comp, scomp, ep, dim, asc0, des0 ) generalize :: Perm a => (Perm0 -> b) -> a -> b@@ -159,6 +161,11 @@ comp :: Perm a => a -> Int comp = generalize I.comp +-- | The number of skew components. E.g., @[5,7,4,6,3,1,0,2]@ has three+-- skew components: @[5,7,4,6]@, @[3]@ and @[1,0,2]@.+scomp :: Perm a => a -> Int+scomp = generalize I.scomp+ -- | The rank as defined by Elizalde and Pak [Bijections for -- refined restricted permutations, /J. Comb. Theory, Ser. A/, 2004]: -- @@ -181,3 +188,8 @@ -- index @i@ such that @w[i] == w[i+1] + 1@. des0 :: Perm a => a -> Int des0 = generalize I.des0++-- | The size of the shadow of @w@. That is, the number of different+-- one point deletions of @w@.+shad :: Perm a => a -> Int+shad = length . shadow . st
sym.cabal view
@@ -1,5 +1,5 @@ Name: sym-Version: 0.4+Version: 0.4.1 Synopsis: Permutations, patterns, and statistics Description: Definitions for permutations with an emphasis on permutation
tests/Properties.hs view
@@ -168,11 +168,6 @@ prop_coshadow = forAll (resize 50 perm) $ \w -> Sym.coshadow w == coshadow w --- prop_lMaxima =--- forAll perm $ \w -> SV.fromList (rMaxIndices w) == Sym.lMaxima w--- where--- rMaxIndices w = [ head $ elemIndices x w | x <- lMaxima w ]- prop_record f g = forAll perm $ \w -> SV.fromList (recordIndices w) == f w where@@ -198,6 +193,18 @@ prop_rMinima_card = forAll perm $ \w -> S.rmin w == SV.length (Sym.rMinima w) +-- The list of indices of components in a permutation+components w = lMaxima w `cap` rMinima (bubble w)++-- The list of indices of skew components in a permutation+skewComponents w = components $ map (\x -> length w - x - 1) w++prop_components =+ forAll perm $ \w -> components (st w) == SV.toList (Sym.components w)++prop_skewComponents =+ forAll perm $ \w -> skewComponents (st w) == SV.toList (Sym.skewComponents w)+ segments :: [a] -> [[a]] segments [] = [[]] segments (x:xs) = segments xs ++ map (x:) (inits xs)@@ -364,6 +371,8 @@ , ("lMinima/card", check prop_lMinima_card) , ("rMaxima/card", check prop_rMaxima_card) , ("rMinima/card", check prop_rMinima_card)+ , ("components", check prop_components)+ , ("skewComponents", check prop_skewComponents) , ("unrankPerm", check prop_unrankPerm) , ("stackSort", check prop_stackSort) , ("stackSort/231", check prop_stackSort_231)@@ -517,8 +526,11 @@ GT -> cap xs yt -- The number of components in a permutation-comp w = length $ lMaxima w `cap` rMinima (bubble w)+comp = length . components +-- The number of skew components in a permutation+scomp = length . skewComponents+ -- rank a la Elizalde ep = fst . last . filter (\(k,ys) -> all (k<=) ys) . zip [0..] . inits . st @@ -542,6 +554,7 @@ vall = length . valleys dasc = length . doubleAscents ddes = length . doubleDescents+shad = length . shadow prop_asc = forAll perm $ \w -> asc w == S.asc w prop_des = forAll perm $ \w -> des w == S.des w@@ -567,9 +580,11 @@ prop_rir = forAll perm $ \w -> rir w == S.rir w prop_rdr = forAll perm $ \w -> rdr w == S.rdr w prop_comp = forAll perm $ \w -> comp w == S.comp w+prop_scomp = forAll perm $ \w -> scomp w == S.scomp w prop_dim = forAll perm $ \w -> dim w == S.dim w prop_asc0 = forAll perm $ \w -> asc0 w == S.asc0 w prop_des0 = forAll perm $ \w -> des0 w == S.des0 w+prop_shad = forAll perm $ \w -> shad w == S.shad w prop_inv_21 = forAll perm $ \w -> S.inv w == length (Sym.copiesOf (Sym.st "21") w) @@ -598,9 +613,11 @@ , ("rir", check prop_rir) , ("rdr", check prop_rdr) , ("comp", check prop_comp)+ , ("scomp", check prop_scomp) , ("dim", check prop_dim) , ("asc0", check prop_asc0) , ("des0", check prop_des0)+ , ("shad", check prop_shad) , ("inv/21", check prop_inv_21) ]