import math
def C(n, r):
'''C(n, r)->Integer representing the combination of n things taken r at a
time.
n: Number of things in "bag"
r: Number of things taken from the "bag"'''
return math.factorial(n)/(math.factorial(n - r)*math.factorial(r));
def bnStateSpace(n):
'''bnStateSpace(n)->Integer representing a rough approximation of the number
of possible BN configurations
n: The number of nodes in the Bayesian network'''
sumSS = 0;
# A BN with n nodes can have n-1 to n*(n - 1)/2 arcs
# Thus, a BN with 5 nodes can have 4 to 10 arcs
for i in range(n - 1, n*(n - 1)/2 + 1):
# Combinations of max arcs taken i at a time
# representing the number of legal BN configurations with i arcs
sumSS += C(n*(n - 1)/2, i);
return sumSS
# Print out BN state space for BNs with 1 to 10 nodes
for i in range(1, 11):
print '%i: %12.0f' % (i, bnStateSpace(i));
# Calculate BN state space from user input
print 'BN state space: %12.0f' % (bnStateSpace(input("Number of nodes in BN: ")));
# Pause before ending execution
raw_input();