Thomas comments on Open thread, Jul. 03 - Jul. 09, 2017

Thomas 3 Jul 2017 8:38 UTC
2 points
Enjoy this problem!
- Gurkenglas 3 Jul 2017 13:09 UTC
  1 point
  Parent
  Your huffman codes with essential indifference are binary trees (each node has 0 or 2 children) with isomorphism.
  
  Let f(n) be the number of trees with n leaves.
```
f(1)=1
f(2n+1)=sum from i=1 to n of f(i)*f(2n+1-i)
f(2n)=f(n)*(f(n)+1)/2 + sum from i=1 to n-1 of f(i)*f(2n-i)
```
  Here’s the first 26 numbers of such trees:
  
  [1,1,1,2,3,6,11,23,46,98,207,451,983,2179,4850,10905, 24631,56011,127912,293547,676157,1563372,3626149,8436379,19680277]
  - Thomas 3 Jul 2017 15:26 UTC
    0 points
    Parent
    It’s something. But what are the codes? An algorithm to create them would suffice. A faster one is better, of course.
    - Gurkenglas 3 Jul 2017 20:54 UTC
      1 point
      Parent
      The same control flow generates them. In Haskell:
      
      data T = N T T | L deriving Show ⠀ ts :: Int -> [T] ts 1 = [L] ts k | (n, 1) <- divMod k 2 = [N x y | i <- [1..n ], x <- ts i, y <- ts (k-i)] ts k | (n, 0) <- divMod k 2 = [N x y | i <- [1..n-1], x <- ts i, y <- ts (k-i)] ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀++ [N x y | ys@(x:_) <- tails (ts n), y <- ys] ⠀ ⠀ <Gurkenglas> > ts 4 <lambdabot> [N L (N L (N L L)),N (N L L) (N L L)]
      (Beware, I had to use U+2800 to almost align the code block in spite of LW’s software eating whitespace. Source here)
      
      Edit: See also: oeis, where you enter an integer sequence and it tells you where people have seen it.
      - Thomas 5 Jul 2017 7:37 UTC
        0 points
        Parent
        Very well, congratulations again!
        
        Perhaps a nonrecursive function would be faster.
        Gurkenglas 5 Jul 2017 14:36 UTC
        0 points
        Parent
        Not really, the sequence grows quickly enough to outstrip the recursive overhead. To calculate the overhead, replace the * in f(i)*f(2n+1-i) with a +. Memoizing is of course trivial anyway, using memoFix.