fhtr

art with code

2010-08-31

Branching factor generator

A function to generate a stream of tree branching factors to approximate a non-integer branching factor.
`branches' x i sum =   let v = (if sum/i > x then floor x else ceiling x) :: Int in   v : branches' x (i+1) (sum+fromIntegral v)branches n = branches' n 0 0       e_branches = branches (exp 1)e_100000 = take 100000 \$ e_branchesaverage l = sum l / fromIntegral (length l)average \$ map fromIntegral e_100000 == 2.71828`

You could also write the average function as
`average2 l = snd \$ foldl (\(i, avg) e -> (i+1, (avg*(i-1) + e)/i)) (1, 0) l average2 \$ map fromIntegral e_100000`

even though that is less accurate. You can use a similar trick for the branches' function to use a running average instead of a running sum.
`branches2' x i avg =   let v = (if avg > x then floor x else ceiling x) :: Int in   v : branches2' x (i+1) ((avg*(i-1)+fromIntegral v)/i)branches2 n = branches2' n 1 0       average \$ map fromIntegral \$ take 100000 \$ branches2 (exp 1)`

To generate a tree of wanted size out of the branching factor list, you'd have a tree generator that eats values off the list and generates tree nodes breadth-first. It is kind of a pain to write.