sym 0.2 → 0.2.1

raw patch · 4 files changed

+50/−4 lines, 4 files

Files

• Math/Sym.hs +17/−1
• Math/Sym/Internal.hs +20/−0
• sym.cabal +1/−1
• tests/Properties.hs +12/−2

@@ -42,6 +42,10 @@     , avoiders        -- :: Perm a => [StPerm] -> [a] -> [a]     , av              -- :: [StPerm] -> Int -> [StPerm] +    -- * Single point deletions+    , del             -- :: Perm a => Int -> a -> a+    , shadow          -- :: (Ord a, Perm a) => a -> [a]+     -- * Simple permutations     , simple          -- :: Perm a => a -> Bool @@ -54,7 +58,7 @@ import Data.Ord (comparing) import Data.Monoid (Monoid(..)) import Data.Bits (Bits, bitSize, testBit, popCount, shiftL)-import Data.List (sort, sortBy)+import Data.List (sort, sortBy, group) import Data.Vector.Storable (Vector) import qualified Data.Vector.Storable as SV (Vector, toList, fromList, fromListN, empty, map, (++)) import qualified Math.Sym.Internal as I@@ -303,6 +307,18 @@ --  av :: [StPerm] -> Int -> [StPerm] av ps = avoiders ps . sym+++-- Single point deletions+-- ----------------------++-- | Delete the element at a given position+del :: Perm a => Int -> a -> a+del i = generalize $ fromVector . I.del i .toVector++-- | The list of all single point deletions+shadow :: (Ord a, Perm a) => a -> [a]+shadow w = map head . group $ sort [ del i w | i <- [0 .. size w - 1]]   -- Simple permutations

@@ -82,6 +82,9 @@     , stackSort     , bubbleSort +    -- * Single point deletions+    , del+     -- * Bitmasks     , onesCUInt     , nextCUInt@@ -473,6 +476,23 @@ -- | One pass of bubble-sort. bubbleSort :: Perm0 -> Perm0 bubbleSort = sortop c_bubblesort++-- Single point deletions+-- ----------------------++-- | Delete the element at a given position+del :: Int -> Perm0 -> Perm0+del i u = runST $ do+  let n = SV.length u+  let j = (SV.!) u i+  v <- MV.unsafeNew (n-1)+  forM_ [0..i-1] $ \k -> do+            let m = (SV.!) u k+            MV.unsafeWrite v k (if m < j then m else m-1)+  forM_ [i+1..n-1] $ \k -> do+            let m = (SV.!) u k+            MV.unsafeWrite v (k-1) (if m < j then m else m-1)+  SV.unsafeFreeze v   -- Bitmasks

@@ -1,5 +1,5 @@ Name:                sym-Version:             0.2+Version:             0.2.1 Synopsis:            Permutations, patterns, and statistics Description:            Definitions for permutations with an emphasis on permutation

@@ -153,6 +153,16 @@ prop_ordiso2 =     forAll perm2 $ \(u,v) -> u `Sym.ordiso` v  ==  (Sym.inverse u `Sym.act` v == Sym.idperm v) +shadow :: Ord a => [a] -> [[a]]+shadow w = nubSort . map normalize $ ptDeletions w+    where+      normalize u = [ (sort w)!!i | i <- st u ]+      nubSort = map head . group . sort+      ptDeletions [] = []+      ptDeletions xs@(x:xt) = xt : map (x:) (ptDeletions xt)++prop_shadow = forAll perm $ \w -> Sym.shadow w == shadow w+ segments :: [a] -> [[a]] segments [] = [[]] segments (x:xs) = segments xs ++ map (x:) (inits xs)@@ -172,8 +182,7 @@ simple :: Ord a => [a] -> Bool simple = null . properIntervals -prop_simple =-    forAll (resize 50 perm) $ \w -> Sym.simple w == simple w+prop_simple = forAll (resize 50 perm) $ \w -> Sym.simple w == simple w  prop_unrankPerm =     forAll perm $ \w ->@@ -308,6 +317,7 @@     , ("inverse",                        check prop_inverse)     , ("ordiso/1",                       check prop_ordiso1)     , ("ordiso/2",                       check prop_ordiso2)+    , ("shadow",                         check prop_shadow)     , ("simple",                         check prop_simple)     , ("unrankPerm",                     check prop_unrankPerm)     , ("stackSort",                      check prop_stackSort)