Skip to content

Instantly share code, notes, and snippets.

@gautambak
Created May 29, 2012 19:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gautambak/9493d7f6f1f47561ea0c to your computer and use it in GitHub Desktop.
Save gautambak/9493d7f6f1f47561ea0c to your computer and use it in GitHub Desktop.
Finding number of bounded premuations
import math
def nCr(n,r):
f = math.factorial
return f(n) / f(r) / f(n-r)
def itemCount_cal(target, items, minValue):
return target- items*minValue
def distributions(itemCount, bucketCount):
#get all possible solutions
f = math.factorial
return f(itemCount)/(f(itemCount-bucketCount) * f(bucketCount))
if __name__ == '__main__':
target_range = 100
bucketCount = 4
lowerLimit = 20
upperLimit = 60
itemCount = itemCount_cal(target_range,bucketCount,lowerLimit)
a = bucketCount * distributions((upperLimit+1) -itemCount, bucketCount)
b = nCr(bucketCount,2) * distributions(2*(upperLimit+1)-itemCount, bucketCount)
c = nCr(bucketCount,3) * distributions(3*(upperLimit+1)-itemCount, bucketCount)
print c - a - b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment