import numpy as np
### # This is a smoke test. That fails.
### # A one-digit number with 10 digit choices
### # should yield k-1.
### k = 10
### m = 1
### N = 1
### # The following gives 126 = 252/2
### # We expect 252 = 10!/(5! 5!)
### # Divided by 2 if ignoring numbers starting with 0
### k = 2
### m = 5
### N = 10
### # Number of outcomes should be 340
### k = 3
### m = 3
### N = 6
### k = 10
### m = 1
### N = 2
# Real problem:
k = 10
m = 3
N = 18
solution_count = 0
factorials = {}
def main():
global solution_count
n_tuple = [None,]*k
recursive_method(n_tuple,1)
print("Total number of permutations:")
print("%d"%(solution_count))
def recursive_method( n_tuple, ni ):
"""
Use recursive backtracking to form all possible
combinations of k digits into N-digit numbers
such that the number of digits is m or less.
(n_tuple is actually a list.)
ni = current class step 1..(k-1)
n_tuple = list of number of digits for each class 0 through k
"""
global solution_count, k, m, N
if(ni==k):
# N_1 through N_(k-1) have been set,
# now it is time to set N_0:
# N_0 = N - N_1 - N_2 - N_3 - .. - N_{k-1}
sum_N = np.sum([n_tuple[j] for j in range(1,k)])
n_tuple[0] = max(0, N-sum_N)
# Compute multiset permutation
solution_count += multiset(N,n_tuple) - multiset_0(N,n_tuple)
return
else:
# Problem: we are not stopping
# when the sum of digits chosen
# is greater than N
# Assemble the minimum and maximum limits for N_i:
# (Everything up to ni-1 should be defined, no TypeErrors due to None)
sum_N = np.sum([n_tuple[j] for j in range(1,ni)])
ktm = (k - ni)*m
expr = N - sum_N - ktm
minn = int(max( 0, expr ))
# Note: previously this was just maxx=m.
# This required a check around each call to
# recursive_method to see if the sum of n_tuple
# was already maxed out. Now we just do it here.
maxx = min(m, N-sum_N)
for N_i in range(minn,maxx+1):
# Set
n_tuple[ni] = N_i
# Explore
recursive_method(n_tuple, ni+1)
# Unset
n_tuple[ni] = None
return
def multiset(N, n_tuple):
"""
Number of multiset permutations
"""
r = factorial(N)/(np.product([factorial(j) for j in n_tuple]))
return r
def multiset_0(N, n_tuple):
"""
Number of multiset permutations that start with 0
"""
if(n_tuple[0]>0):
r = factorial(N-1)/(np.product([factorial(j-1) if(i==0) else factorial(j) for i,j in enumerate(n_tuple)]))
return r
else:
return 0
def factorial(n):
"""
Factorial utility
"""
if(n<0):
raise Exception("Error: negative factorials not possible")
if(n==1 or n==0):
return 1
else:
return n*factorial(n-1)
if __name__=="__main__":
main()