sym 0.3 → 0.4
raw patch · 7 files changed
+98/−92 lines, 7 files
Files
- Math/Sym.hs +33/−2
- Math/Sym/Internal.hs +26/−27
- Math/Sym/Stat.hs +0/−12
- cbits/stat.c +0/−35
- include/stat.h +0/−3
- sym.cabal +1/−1
- tests/Properties.hs +38/−12
Math/Sym.hs view
@@ -20,6 +20,7 @@ , toList -- :: StPerm -> [Int] , fromList -- :: [Int] -> StPerm , (/-/) -- :: StPerm -> StPerm -> StPerm+ , bijection -- :: StPerm -> Int -> Int , unrankStPerm -- :: Int -> Integer -> StPerm , sym -- :: Int -> [StPerm] @@ -50,6 +51,12 @@ , ext -- :: Perm a => Int -> a -> a , coshadow -- :: (Ord a, Perm a) => a -> [a] + -- * Left-to-right maxima and similar functions+ , lMaxima -- :: Perm a => a -> Set+ , lMinima -- :: Perm a => a -> Set+ , rMaxima -- :: Perm a => a -> Set+ , rMinima -- :: Perm a => a -> Set+ -- * Simple permutations , simple -- :: Perm a => a -> Bool @@ -65,7 +72,7 @@ import Data.List (sort, sortBy, group) import Data.Vector.Storable (Vector) import qualified Data.Vector.Storable as SV- ( Vector, toList, fromList, fromListN, empty, singleton+ ( (!), Vector, toList, fromList, fromListN, empty, singleton , length, map, concat, splitAt ) import qualified Math.Sym.Internal as I@@ -124,6 +131,10 @@ u' = SV.map ( + size v) $ toVector u v' = toVector v +-- | The bijective function defined by a standard permutation.+bijection :: StPerm -> Int -> Int+bijection w = (SV.!) (toVector w)+ -- | @unrankStPerm n rank@ is the @rank@-th (Myrvold & Ruskey) -- permutation of @[0..n-1]@. E.g., -- @@ -343,7 +354,8 @@ shadow :: (Ord a, Perm a) => a -> [a] shadow w = map head . group $ sort [ del i w | i <- [0 .. size w - 1]] --- | Insert a new largest element at the given position+-- | Extend a permutation by inserting a new largest element at the+-- given position ext :: Perm a => Int -> a -> a ext i = generalize' $ fromVector . ext0 . toVector where@@ -356,6 +368,25 @@ coshadow :: (Ord a, Perm a) => a -> [a] coshadow w = map head . group $ sort [ ext i w | i <- [0 .. size w]] ++-- Left-to-right maxima and similar functions+-- ------------------------------------------++-- | The set of indices of left-to-right maxima.+lMaxima :: Perm a => a -> Set+lMaxima = I.lMaxima . toVector . st++-- | The set of indices of left-to-right minima.+lMinima :: Perm a => a -> Set+lMinima = I.lMaxima . I.complement . toVector . st++-- | The set of indices of right-to-left maxima.+rMaxima :: Perm a => a -> Set+rMaxima = I.rMaxima . toVector . st++-- | The set of indices of right-to-left minima.+rMinima :: Perm a => a -> Set+rMinima = I.rMaxima . I.complement . toVector . st -- Simple permutations -- -------------------
Math/Sym/Internal.hs view
@@ -82,9 +82,9 @@ , asc0 -- small ascents , des0 -- small descents - -- * List valued permutation statistics- , lminValues- , lminIndices+ -- * Left-to-right maxima, etc+ , lMaxima+ , rMaxima -- * Sorting operators , stackSort@@ -387,11 +387,11 @@ last :: Perm0 -> Int last = SV.last --- | The number of right-to-left minima.+-- | The number of left-to-right minima. rmin :: Perm0 -> Int rmin = lmin . SV.reverse --- | The number of right-to-left maxima.+-- | The number of left-to-right maxima. rmax :: Perm0 -> Int rmax = lmax . SV.reverse @@ -487,31 +487,30 @@ des0 :: Perm0 -> Int des0 = stat c_des0 --- Vector valued permutation statistics--- ------------------------------------foreign import ccall unsafe "stat.h lmin_values" c_lmin_values- :: Ptr CLong -> Ptr CLong -> CLong -> IO CLong--foreign import ccall unsafe "stat.h lmin_indices" c_lmin_indices- :: Ptr CLong -> Ptr CLong -> CLong -> IO CLong+-- Left-to-right maxima, etc+-- ------------------------- -record :: (Ptr CLong -> Ptr CLong -> CLong -> IO CLong) -> Perm0 -> SV.Vector Int-record f w = unsafePerformIO $ do- let n = SV.length w- v <- MV.unsafeNew n- SV.unsafeWith w $ \w_ptr ->- MV.unsafeWith v $ \v_ptr -> do- k <- f (castPtr v_ptr) (castPtr w_ptr) (fromIntegral n)- SV.unsafeFreeze $ MV.unsafeSlice 0 (fromIntegral k) v+-- | The list of indices of left-to-right maxima.+lMaxima :: Perm0 -> SV.Vector Int+lMaxima 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' = (SV.!) w (n-i)+ if m' > m then do+ MV.unsafeWrite v j (n-i)+ (+1) `liftM` iter v (i-1) (j+1) m'+ else+ iter v (i-1) j m --- | The list of values of left-to-right minima-lminValues :: Perm0 -> SV.Vector Int-lminValues = record c_lmin_values+rMaxima :: Perm0 -> SV.Vector Int+rMaxima w = SV.reverse . SV.map (\x -> SV.length w - x - 1) . lMaxima $ reverse w --- | The list of indices of left-to-right minima-lminIndices :: Perm0 -> SV.Vector Int-lminIndices = record c_lmin_indices -- Sorting operators -- -----------------
Math/Sym/Stat.hs view
@@ -46,8 +46,6 @@ , dim -- dimension , asc0 -- small ascents , des0 -- small descents- , lminValues- , lminIndices ) where import Prelude hiding (head, last)@@ -57,9 +55,7 @@ ( 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- , lminValues, lminIndices )-import qualified Data.Vector.Storable as SV (toList) generalize :: Perm a => (Perm0 -> b) -> a -> b generalize f = f . toVector . st@@ -185,11 +181,3 @@ -- index @i@ such that @w[i] == w[i+1] + 1@. des0 :: Perm a => a -> Int des0 = generalize I.des0---- | The list of values of left-to-right minima-lminValues :: Perm a => a -> [Int]-lminValues = generalize (SV.toList . I.lminValues)---- | The list of indices of left-to-right minima-lminIndices :: Perm a => a -> [Int]-lminIndices = generalize (SV.toList . I.lminIndices)
cbits/stat.c view
@@ -320,38 +320,3 @@ } return acc; }---/* The array of left-to-right minima */-long-lmin_values(long *v, const long *w, long len)-{- long m = *w + 1;- long acc = 0;-- for (; len > 0; len--, w++) {- if (*w < m) {- m = *w;- acc++;- *(v++) = m;- }- }- return acc;-}--/* The array of indices of left-to-right minima */-long-lmin_indices(long *v, const long *w, long len)-{- long i, m = *w + 1;- long acc = 0;-- for (i = 0; i < len; i++, w++) {- if (*w < m) {- m = *w;- acc++;- *(v++) = i;- }- }- return acc;-}
include/stat.h view
@@ -19,6 +19,3 @@ long dim (const long *, long); /* dimension */ long asc0 (const long *, long); /* small ascents */ long des0 (const long *, long); /* small descents */--long lmin_values (long *, const long *, long); /* values of left-to-right minima */-long lmin_indices (long *, const long *, long); /* indices of left-to-right minima */
sym.cabal view
@@ -1,5 +1,5 @@ Name: sym-Version: 0.3+Version: 0.4 Synopsis: Permutations, patterns, and statistics Description: Definitions for permutations with an emphasis on permutation
tests/Properties.hs view
@@ -168,6 +168,36 @@ 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+ recordIndices w = [ head $ elemIndices x w | x <- g w ]++prop_lMaxima = prop_record Sym.lMaxima lMaxima++prop_lMinima = prop_record Sym.lMinima lMinima++prop_rMaxima = prop_record Sym.rMaxima rMaxima++prop_rMinima = prop_record Sym.rMinima rMinima++prop_lMaxima_card =+ forAll perm $ \w -> S.lmax w == SV.length (Sym.lMaxima w)++prop_lMinima_card =+ forAll perm $ \w -> S.lmin w == SV.length (Sym.lMinima w)++prop_rMaxima_card =+ forAll perm $ \w -> S.rmax w == SV.length (Sym.rMaxima w)++prop_rMinima_card =+ forAll perm $ \w -> S.rmin w == SV.length (Sym.rMinima w)+ segments :: [a] -> [[a]] segments [] = [[]] segments (x:xs) = segments xs ++ map (x:) (inits xs)@@ -326,6 +356,14 @@ , ("shadow", check prop_shadow) , ("coshadow", check prop_coshadow) , ("simple", check prop_simple)+ , ("lMaxima", check prop_lMaxima)+ , ("lMinima", check prop_lMinima)+ , ("rMaxima", check prop_rMaxima)+ , ("rMinima", check prop_rMinima)+ , ("lMaxima/card", check prop_lMaxima_card)+ , ("lMinima/card", check prop_lMinima_card)+ , ("rMaxima/card", check prop_rMaxima_card)+ , ("rMinima/card", check prop_rMinima_card) , ("unrankPerm", check prop_unrankPerm) , ("stackSort", check prop_stackSort) , ("stackSort/231", check prop_stackSort_231)@@ -535,15 +573,6 @@ prop_inv_21 = forAll perm $ \w -> S.inv w == length (Sym.copiesOf (Sym.st "21") w) -prop_lmin_values =- forAll perm $ \w -> lMinima (st w) == S.lminValues w-prop_lmin_indices =- forAll perm $ \w -> [ head $ elemIndices x w | x <- lMinima w ] == S.lminIndices w-prop_lmin_card =- forAll perm $ \w -> and [ S.lmin w == length (S.lminValues w)- , S.lmin w == length (S.lminIndices w)- ]- testsStat = [ ("asc", check prop_asc) , ("des", check prop_des)@@ -573,9 +602,6 @@ , ("asc0", check prop_asc0) , ("des0", check prop_des0) , ("inv/21", check prop_inv_21)- , ("lmin/values", check prop_lmin_values)- , ("lmin/indices", check prop_lmin_indices)- , ("lmin/card", check prop_lmin_card) ] ---------------------------------------------------------------------------------