Skip to content

Instantly share code, notes, and snippets.

@tzengyuxio
Created July 9, 2014 19:38
Show Gist options
  • Save tzengyuxio/554c26d9300e455438be to your computer and use it in GitHub Desktop.
Save tzengyuxio/554c26d9300e455438be to your computer and use it in GitHub Desktop.
#!/usr/local/bin/python2.7
import math
NUM_DIGITS = 7
def C(m, n):
if m < n: return 0
if m <= 0: return 0
if n == 0 or n == m: return 1
n = min(n, m-n)
if (m, n) in C.table: return C.table[(m, n)]
rs = math.factorial(m) / math.factorial(n) / math.factorial(m-n)
C.table[(m, n)] = rs
return rs
def ConvertIndexToBinaryState(idx, numDigits):
oneCount = 0
inGroup = idx
# afther this loop, we can get the values of oneCount and inGroup
for i in range(numDigits):
if inGroup >= C(numDigits, i):
oneCount += 1
inGroup -= C(numDigits, i)
else:
break
# generate binary string
s = ""
for i in range(numDigits-1, -1, -1):
if oneCount == 0:
s += '0'
elif inGroup >= C(i, oneCount):
s += '1'
inGroup -= C(i, oneCount)
oneCount -= 1
else:
s += '0'
return s
C.table = {} # initial static dictionary variable in function
upperLimit = pow(2, NUM_DIGITS)
for i in range(upperLimit):
print "%6d => %s" % (i, ConvertIndexToBinaryState(i, NUM_DIGITS))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment