Implemented the RANRUT algorithm, with tests.

Implementation of the RANRUT algorithm with tests.

src/treex/simulation.py

@@ -102,4 +102,74 @@ def gen_random_tree(size,degree=None,height=None):
     # t.erase_attribute('label_for_simulation') # Erase labels: 'label for simulation'
     return t
 
-# --------------------------------------------------------------
\ No newline at end of file
+# --------------------------------------------------------------
+
+def __recursive_number_of_unordered_trees(n,dico):
+    sum=0
+    for d in range(1,n):
+        for j in range(1,math.floor((n-1)/d)+1):
+            if n-j*d not in dico:
+                __recursive_number_of_unordered_trees(n-j*d,dico)
+            if d not in dico:
+                __recursive_number_of_unordered_trees(d,dico)
+            sum+=d*dico[n-j*d]*dico[d]
+    dico[n]=int(sum/(n-1))
+
+def __random_pair(n,dico):
+    p = random.random()
+    cumsum=0
+    for d in range(n-1,0,-1):
+        for j in range(1,math.floor((n-1)/d)+1):
+            cumsum+=d*dico[n-j*d]*dico[d]/(dico[n]*(n-1))
+            if p<cumsum:
+                return (j,d)
+
+def __recursive_ranrut_tree(n,dico):
+    if n==1:
+        return Tree()
+    elif n==2:
+        t1=Tree()
+        t1.add_subtree(Tree())
+        return t1
+    else:
+        j,d = __random_pair(n,dico)
+
+        t1 = __recursive_ranrut_tree(n-j*d,dico)
+        t2 = __recursive_ranrut_tree(d,dico)
+
+        t_list = [t2.copy() for i in range(j)]
+        for t in t_list:
+            t1.add_subtree(t)
+    return t1
+
+def gen_ranrut_tree(size):
+    """
+    Sample a tree from the uniform distribution of unordered trees of the given size, with the RANRUT algorithm [1].
+
+    :param size: int
+
+    :returns:  Tree
+
+    Warning
+    -------
+    The complexity of the algorithm [2] is in average of the order :math:`O(n^2\\log n)` for the pre-processing part, and :math:`O(n\\log n)` for the actual simulation.
+    Therefore, depending on your machine, large values of ``size`` might be intractable.
+
+    References
+    ----------
+    [1] Nijenhuis, Albert, and H. S. Wilf. "Combinatorial Algorithms Academic Press." New York (1978).
+
+    [2] Alonso, L., R. Schott, and INRIA-Lorraine CRIN. "Random Unlabelled Rooted Trees Revisited." Proc. ICCI. Vol. 94. 1994.
+
+
+    """
+    if size==1:
+        return Tree()
+    elif size==2:
+        t1=Tree()
+        t1.add_subtree(Tree())
+        return t1
+    else:
+        dico = {1: 1}
+        __recursive_number_of_unordered_trees(size, dico)
+        return __recursive_ranrut_tree(size,dico)
\ No newline at end of file