List and Unrank for Binary Trees of a Given Number of Internal Nodes

In [ ]:

    

def listTree(n):
    if n == 0:
        return [None]
    else:
        res = []
        for i in range(n):
            for g in listTree(i):
                for d in listTree(n-1-i):
                    res.append((g,d))
        return res


    

In [2]:

    

for t in listTree(3): print t


    

    




(None, (None, (None, None)))
(None, ((None, None), None))
((None, None), (None, None))
((None, (None, None)), None)
(((None, None), None), None)

In [ ]:

    




    

In [3]:

    

@cached_function
def catalan(n):
    print "Calcul de catalan(%i)"%n
    if n == 0:
        return 1
    else: 
        return sum(catalan(i)*catalan(n-1-i) for i in range(n))


    

In [4]:

    

catalan(10)


    

    




Calcul de catalan(10)
Calcul de catalan(0)
Calcul de catalan(9)
Calcul de catalan(8)
Calcul de catalan(7)
Calcul de catalan(6)
Calcul de catalan(5)
Calcul de catalan(4)
Calcul de catalan(3)
Calcul de catalan(2)
Calcul de catalan(1)






    
Out[4]:





16796

In [5]:

    

[catalan(i) for i in range(10)]


    

    
Out[5]:





[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

In [ ]:

    




    

In [6]:

    

def unrankTree(n, i):
    if i >= catalan(n):
        raise ValueError, (n, i)
    elif n == 0:
        return None
    else:
        ng = 0
        while i >= catalan(ng) * catalan(n-1-ng):
            i -= catalan(ng) * catalan(n-1-ng)
            ng += 1
        ig = i // catalan(n-1-ng)
        id = i % catalan(n-1-ng)
        return (unrankTree(ng, ig), unrankTree(n-1-ng, id))


    

In [7]:

    

N = 10
l = [unrankTree(N, i) for i in range(catalan(N))]
l == listTree(N)


    

    
Out[7]:





True

In [8]:

    

N = 100


    

In [9]:

    

c = catalan(100)


    

    




Calcul de catalan(100)
Calcul de catalan(99)
Calcul de catalan(98)
Calcul de catalan(97)
Calcul de catalan(96)
Calcul de catalan(95)
Calcul de catalan(94)
Calcul de catalan(93)
Calcul de catalan(92)
Calcul de catalan(91)
Calcul de catalan(90)
Calcul de catalan(89)
Calcul de catalan(88)
Calcul de catalan(87)
Calcul de catalan(86)
Calcul de catalan(85)
Calcul de catalan(84)
Calcul de catalan(83)
Calcul de catalan(82)
Calcul de catalan(81)
Calcul de catalan(80)
Calcul de catalan(79)
Calcul de catalan(78)
Calcul de catalan(77)
Calcul de catalan(76)
Calcul de catalan(75)
Calcul de catalan(74)
Calcul de catalan(73)
Calcul de catalan(72)
Calcul de catalan(71)
Calcul de catalan(70)
Calcul de catalan(69)
Calcul de catalan(68)
Calcul de catalan(67)
Calcul de catalan(66)
Calcul de catalan(65)
Calcul de catalan(64)
Calcul de catalan(63)
Calcul de catalan(62)
Calcul de catalan(61)
Calcul de catalan(60)
Calcul de catalan(59)
Calcul de catalan(58)
Calcul de catalan(57)
Calcul de catalan(56)
Calcul de catalan(55)
Calcul de catalan(54)
Calcul de catalan(53)
Calcul de catalan(52)
Calcul de catalan(51)
Calcul de catalan(50)
Calcul de catalan(49)
Calcul de catalan(48)
Calcul de catalan(47)
Calcul de catalan(46)
Calcul de catalan(45)
Calcul de catalan(44)
Calcul de catalan(43)
Calcul de catalan(42)
Calcul de catalan(41)
Calcul de catalan(40)
Calcul de catalan(39)
Calcul de catalan(38)
Calcul de catalan(37)
Calcul de catalan(36)
Calcul de catalan(35)
Calcul de catalan(34)
Calcul de catalan(33)
Calcul de catalan(32)
Calcul de catalan(31)
Calcul de catalan(30)
Calcul de catalan(29)
Calcul de catalan(28)
Calcul de catalan(27)
Calcul de catalan(26)
Calcul de catalan(25)
Calcul de catalan(24)
Calcul de catalan(23)
Calcul de catalan(22)
Calcul de catalan(21)
Calcul de catalan(20)
Calcul de catalan(19)
Calcul de catalan(18)
Calcul de catalan(17)
Calcul de catalan(16)
Calcul de catalan(15)
Calcul de catalan(14)
Calcul de catalan(13)
Calcul de catalan(12)
Calcul de catalan(11)

In [10]:

    

h = randint(0, c); h


    

    
Out[10]:





45230921115097425702465058175213294713723592626875170549L

In [11]:

    

unrankTree(N, h)


    

    
Out[11]:





(None,
 (None,
  ((None,
    (((None,
       (None,
        ((None, ((None, None), None)),
         ((None,
           (None,
            (((None, (None, (None, ((None, None), (None, None))))), None),
             (((None, None), ((None, None), None)),
              ((None,
                ((None, None),
                 ((None, (None, None)),
                  (None,
                   (None,
                    ((((None, None), None),
                      (None,
                       ((((None, None),
                          (None,
                           (((None, (((None, None), None), None)),
                             (None, None)),
                            ((None, None), None)))),
                         None),
                        (None, (None, None))))),
                     (((None, (None, None)), None), (None, None)))))))),
               None))))),
          None)))),
      ((None, ((None, None), (None, None))),
       (((((None, (None, None)), None), (None, None)), None),
        ((None,
          ((((None, None), ((None, None), (None, None))), None),
           (((None, ((None, None), None)), (None, None)), None))),
         (None, None))))),
     (None,
      ((None, None), ((((None, None), None), ((None, None), None)), None))))),
   None)))

In [12]:

    

def prof(tr):
    if tr is None: return 0
    else: 
        return 1+max(prof(tr[0]), prof(tr[1]))


    

In [13]:

    

prof(unrankTree(N, h))


    

    
Out[13]:





33

In [ ]: