module Combinatorics.TreeDepth (
treeDepth,
treeDepthSeq,
nodeDepth,
nodeDegreeProb,
nodeDegreeExpect,
) where
import qualified Polynomial as Poly
import qualified Data.Map as Map
import Data.Ratio ((%), )
nodeDepth :: [[Integer]]
nodeDepth :: [[Integer]]
nodeDepth = forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (forall a b c. (a -> b -> c) -> b -> a -> c
flip Integer -> [Integer] -> [Integer]
nodeDepthIt) [Integer
1] [Integer
1 ..]
nodeDepthIt :: Integer -> [Integer] -> [Integer]
nodeDepthIt :: Integer -> [Integer] -> [Integer]
nodeDepthIt Integer
n = forall a. Num a => [a] -> [a] -> [a]
Poly.mul [Integer
n,Integer
1]
type TreeFreq = Map.Map [Integer] Integer
treeDepth :: [Rational]
treeDepth :: [Rational]
treeDepth =
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Integral a => a -> a -> Ratio a
(%)
(forall a b. (a -> b) -> [a] -> [b]
map (forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (\([Integer]
xs,Integer
c) -> forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (t :: * -> *) a. Foldable t => t a -> Int
length [Integer]
xs) forall a. Num a => a -> a -> a
* Integer
c) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Map k a -> [(k, a)]
Map.toList)
[Map [Integer] Integer]
treePrototypes)
(forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl forall a. Num a => a -> a -> a
(*) Integer
1 [Integer
1 ..])
treeDepthSeq :: [[Integer]]
treeDepthSeq :: [[Integer]]
treeDepthSeq =
let count :: Map [a] Integer -> [Integer]
count = forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Map k a -> [(k, a)]
Map.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith forall a. Num a => a -> a -> a
(+) forall b c a. (b -> c) -> (a -> b) -> a -> c
.
forall a b. (a -> b) -> [a] -> [b]
map (\([a]
xs,Integer
c) -> (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs, Integer
c)) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Map k a -> [(k, a)]
Map.toList
in forall a b. (a -> b) -> [a] -> [b]
map forall {a}. Map [a] Integer -> [Integer]
count [Map [Integer] Integer]
treePrototypes
treePrototypes :: [TreeFreq]
treePrototypes :: [Map [Integer] Integer]
treePrototypes =
forall a. (a -> a) -> a -> [a]
iterate Map [Integer] Integer -> Map [Integer] Integer
treeDepthIt (forall k a. k -> a -> Map k a
Map.singleton [Integer
1] Integer
1)
extendTree :: [Integer] -> [[Integer]]
extendTree :: [Integer] -> [[Integer]]
extendTree [Integer]
tree =
forall a. [a] -> [a]
tail (forall a b. (a, b) -> b
snd (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
(\Integer
x ([Integer]
xs,[[Integer]]
ys) -> (Integer
xforall a. a -> [a] -> [a]
:[Integer]
xs, ((Integer
xforall a. Num a => a -> a -> a
+Integer
1)forall a. a -> [a] -> [a]
:[Integer]
xs) forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
map (Integer
xforall a. a -> [a] -> [a]
:) [[Integer]]
ys)) ([],[]) [Integer]
tree)) forall a. [a] -> [a] -> [a]
++
[[Integer]
tree forall a. [a] -> [a] -> [a]
++ [Integer
1]]
treeDepthIt :: TreeFreq -> TreeFreq
treeDepthIt :: Map [Integer] Integer -> Map [Integer] Integer
treeDepthIt Map [Integer] Integer
fm =
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith forall a. Num a => a -> a -> a
(+)
(forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\([Integer]
xs,Integer
c) -> forall a b. [a] -> [b] -> [(a, b)]
zip ([Integer] -> [[Integer]]
extendTree [Integer]
xs) (forall a b. (a -> b) -> [a] -> [b]
map (Integer
cforall a. Num a => a -> a -> a
*) [Integer]
xs))
(forall k a. Map k a -> [(k, a)]
Map.toList Map [Integer] Integer
fm))
nodeDegreeProb :: [[Rational]]
nodeDegreeProb :: [[Rational]]
nodeDegreeProb = forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Integer
den -> forall a b. (a -> b) -> [a] -> [b]
map (forall a. Integral a => a -> a -> Ratio a
%Integer
den)) (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(*) [Integer
1 ..]) [[Integer]]
nodeDegree
nodeDegree :: [[Integer]]
nodeDegree :: [[Integer]]
nodeDegree =
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Integer -> Integer -> [Integer] -> [Integer]
nodeDegreeIt)) [Integer
1]
(forall a b. [a] -> [b] -> [(a, b)]
zip [Integer
0 ..] (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(*) [Integer
1 ..]))
nodeDegreeIt :: Integer -> Integer -> [Integer] -> [Integer]
nodeDegreeIt :: Integer -> Integer -> [Integer] -> [Integer]
nodeDegreeIt Integer
n Integer
nFac = forall a. Num a => [a] -> [a] -> [a]
Poly.add [Integer
nFac] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Num a => [a] -> [a] -> [a]
Poly.mul [Integer
n,Integer
1]
nodeDegreeExpect :: [Rational]
nodeDegreeExpect :: [Rational]
nodeDegreeExpect =
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Integral a => a -> a -> Ratio a
(%) [Integer]
nodeDegreeExpectAux1 (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(*) [Integer
1 ..])
nodeDegreeExpectTrans :: Integer -> [Integer] -> [Integer]
nodeDegreeExpectTrans :: Integer -> [Integer] -> [Integer]
nodeDegreeExpectTrans Integer
s [Integer]
x =
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\Integer
acc (Integer
n,Integer
c) -> Integer
c forall a. Num a => a -> a -> a
+ Integer
nforall a. Num a => a -> a -> a
*Integer
acc) Integer
s
(forall a b. [a] -> [b] -> [(a, b)]
zip [Integer
1 ..] [Integer]
x)
nodeDegreeExpectAux0, nodeDegreeExpectAux1 :: [Integer]
nodeDegreeExpectAux0 :: [Integer]
nodeDegreeExpectAux0 = Integer -> [Integer] -> [Integer]
nodeDegreeExpectTrans Integer
1 (forall a. (a -> a -> a) -> [a] -> [a]
scanl1 forall a. Num a => a -> a -> a
(*) [Integer
1 ..])
nodeDegreeExpectAux1 :: [Integer]
nodeDegreeExpectAux1 = Integer -> [Integer] -> [Integer]
nodeDegreeExpectTrans Integer
0 [Integer]
nodeDegreeExpectAux0