sym 0.2.2 → 0.2.3

raw patch · 6 files changed

+57/−7 lines, 6 files

Files

• Math/Sym.hs +1/−1
• Math/Sym/Internal.hs +8/−0
• Math/Sym/Stat.hs +9/−4
• cbits/stat.c +25/−0
• sym.cabal +1/−1
• tests/Properties.hs +13/−1

@@ -291,7 +291,7 @@ avoids :: Perm a => a -> [StPerm] -> Bool w `avoids` ps = all null [ copiesOf p w | p <- ps ] --- | @avoiders ps v@ is the list of permutations of @v@ avoiding the+-- | @avoiders ps vs@ is the list of permutations in @vs@ avoiding the -- patterns @ps@. This is equivalent to the definition --  -- > avoiders ps = filter (`avoids` ps)

@@ -58,6 +58,7 @@     , des     -- descents     , exc     -- excedances     , fp      -- fixed points+    , cyc     -- cycles     , inv     -- inversions     , maj     -- the major index     , peak    -- peaks@@ -320,6 +321,9 @@ foreign import ccall unsafe "stat.h fp" c_fp     :: Ptr CLong -> CLong -> CLong +foreign import ccall unsafe "stat.h cyc" c_cyc+    :: Ptr CLong -> CLong -> CLong+ foreign import ccall unsafe "stat.h inv" c_inv     :: Ptr CLong -> CLong -> CLong @@ -450,6 +454,10 @@ -- | The number of fixed points. fp :: Perm0 -> Int fp = stat c_fp++-- | The number of cycles.+cyc :: Perm0 -> Int+cyc = stat c_cyc  -- | The number of components. comp :: Perm0 -> Int

@@ -23,6 +23,7 @@     , des         -- descents     , exc         -- excedances     , fp          -- fixed points+    , cyc         -- cycles     , inv         -- inversions     , maj         -- the major index     , peak        -- peaks@@ -52,7 +53,7 @@ import Math.Sym (Perm, toVector, st) import Math.Sym.Internal (Perm0) import qualified Math.Sym.Internal as I -    ( asc, des, exc, fp, inv, maj, peak, vall, dasc, ddes, lmin, lmax, rmin, rmax+    ( asc, des, exc, fp, cyc, inv, maj, peak, vall, dasc, ddes, lmin, lmax, rmin, rmax     , head, last, lir, ldr, rir, rdr, comp, ep, dim, asc0, des0     , lminValues, lminIndices     )@@ -71,15 +72,19 @@ des :: Perm a => a -> Int des = generalize I.des --- | The number of /excedances/: positions @i@ such that @w[i] > i@;+-- | The number of /excedances/: positions @i@ such that @w[i] > i@. exc :: Perm a => a -> Int exc = generalize I.exc --- | The number of /fixed points/: positions @i@ such that @w[i] == i@;+-- | The number of /fixed points/: positions @i@ such that @w[i] == i@. fp :: Perm a => a -> Int fp = generalize I.fp --- | The number of /inversions/: pairs @\(i,j\)@ such that @i \< j@ and @w[i] > w[j]@+-- | The number of /cycles/: orbits of the permutation when viewed as a function.+cyc :: Perm a => a -> Int+cyc = generalize I.cyc++-- | The number of /inversions/: pairs @\(i,j\)@ such that @i \< j@ and @w[i] > w[j]@. inv :: Perm a => a -> Int inv = generalize I.inv 

@@ -56,6 +56,31 @@ }  +/* The number of cycles */+long+cyc(const long *w, long len)+{+	long i = 0;+	long j = 0;+	long acc = 0;+	int *called = malloc(len*sizeof(*called));++	memset(called, 0, len*sizeof(*called));++	while (j < len) {+		j = w[i];+		called[i] = 1;+		if (called[j]) {+			acc++;+			while (j < len && called[j])+				j++;+		}+		i = j;+	}+	return acc;+}++ /* The number of inversions */ long inv(const long *w, long len)

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

@@ -403,10 +403,20 @@ excedances  xs = map fst . filter (\(i,a)->i <  fromIntegral a) $ zip [0..] xs fixedpoints xs = map fst . filter (\(i,a)->i == fromIntegral a) $ zip [0..] xs +orbit :: Eq a => (a -> a) -> a -> [a]+orbit f x = y:takeWhile (/=y) ys where (y:ys) = iterate f x++orbits :: Eq a => (a -> a) -> [a] -> [[a]]+orbits f [] = []+orbits f (x:xs) = ys:orbits f (xs\\ys) where ys = orbit f x+ exc, fp :: [Int] -> Int exc = length . excedances . st fp  = length . fixedpoints . st +cyc :: [Int] -> Int+cyc w = let v = st w in length $ orbits (v!!) v+ runs :: Ord a => (a -> a -> Bool) -> [a] -> [a] -> [[a]] runs _ [] [] = [] runs _ rs [] = [rs]@@ -491,6 +501,7 @@ prop_des  = forAll perm $ \w -> des  w == S.des  w prop_exc  = forAll perm $ \w -> exc  w == S.exc  w prop_fp   = forAll perm $ \w -> fp   w == S.fp   w+prop_cyc  = forAll perm $ \w -> cyc  w == S.cyc  w prop_inv  = forAll perm $ \w -> inv  w == S.inv  w prop_maj  = forAll perm $ \w -> maj  w == S.maj  w prop_lmin = forAll perm $ \w -> lmin w == S.lmin w@@ -503,7 +514,7 @@ prop_vall = forAll perm $ \w -> vall w == S.vall w prop_dasc = forAll perm $ \w -> dasc w == S.dasc w prop_ddes = forAll perm $ \w -> ddes w == S.ddes w-prop_ep   = forAll perm $ \w -> ep   w == S.ep  w+prop_ep   = forAll perm $ \w -> ep   w == S.ep   w prop_lir  = forAll perm $ \w -> lir  w == S.lir  w prop_ldr  = forAll perm $ \w -> ldr  w == S.ldr  w prop_rir  = forAll perm $ \w -> rir  w == S.rir  w@@ -529,6 +540,7 @@     , ("des",          check prop_des)     , ("exc",          check prop_exc)     , ("fp",           check prop_fp)+    , ("cyc",          check prop_cyc)     , ("inv",          check prop_inv)     , ("maj",          check prop_maj)     , ("lmin",         check prop_lmin)