1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#! /usr/bin/env python
##############################################################################
## DendroPy Phylogenetic Computing Library.
##
## Copyright 2010-2015 Jeet Sukumaran and Mark T. Holder.
## All rights reserved.
##
## See "LICENSE.rst" for terms and conditions of usage.
##
## If you use this work or any portion thereof in published work,
## please cite it as:
##
## Sukumaran, J. and M. T. Holder. 2010. DendroPy: a Python library
## for phylogenetic computing. Bioinformatics 26: 1569-1571.
##
##############################################################################
"""
Combinatoric and related functionCombinatoric and related functions.
"""
import math
def factorial(num):
"""factorial(n): return the factorial of the integer num.
factorial(0) = 1
factorial(n) with n<0 is -factorial(abs(n))
"""
result = 1
for i in range(1, abs(num)+1):
result *= i
return result
def choose(population, sample):
"""
Returns ``population`` choose ``sample``, given
by: n! / k!(n-k)!, where n == ``population`` and
k == ``sample``.
"""
if sample > population:
return 0
s = max(sample, population - sample)
assert s <= population
assert population > -1
if s == population:
return 1
numerator = 1
denominator = 1
for i in range(s+1, population + 1):
numerator *= i
denominator *= (i - s)
return numerator/denominator
def num_edges_on_tree(num_leaves, is_rooted=True):
if is_rooted:
return (2 * num_leaves) - 2
else:
return (2 * num_leaves) - 3
def num_internal_nodes_on_tree(num_leaves, is_rooted=True):
if is_rooted:
return num_leaves - 1
else:
return num_leaves - 2
def num_internal_edges_on_tree(num_leaves, is_rooted=True):
if is_rooted:
return num_leaves - 2
else:
return num_leaves - 3
|
