In [1]:

    

def binom(n, k):
    if k < 0 or k > n:
        return 0
    return factorial(n)/(factorial(k)*factorial(n-k))


    

In [2]:

    

[[binom(n, k) for k in range(n+1)] for n in range(11)]


    

    
Out[2]:





[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 7, 1],
 [1, 8, 28, 56, 70, 56, 28, 8, 1],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1],
 [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]]

In [3]:

    

def listBSnk(n, k):
    if k > n: 
        return []
    if k == 0:
        return [n*[0]]
    return ([[0]+x for x in listBSnk(n-1, k)] +
            [[1]+x for x in listBSnk(n-1, k-1)])


    

In [4]:

    

listBSnk(5,2)


    

    
Out[4]:





[[0, 0, 0, 1, 1],
 [0, 0, 1, 0, 1],
 [0, 0, 1, 1, 0],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 1, 1, 0, 0],
 [1, 0, 0, 0, 1],
 [1, 0, 0, 1, 0],
 [1, 0, 1, 0, 0],
 [1, 1, 0, 0, 0]]

In [5]:

    

def rankBSnk(n, k, x):
    if n == 0:
        if k == 0 and x == []:
            return 0
        else:
            raise IndexError
    if k == 0:
        if len(x) == n and all(v == 0 for v in x):
            return 0
        else:
            raise IndexError
    assert k > 0 and n > 0
    if x[0] == 0:
        return rankBSnk(n-1, k, x[1:])
    elif x[0] == 1:
        return binom(n-1, k) + rankBSnk(n-1, k-1, x[1:])
    else:
        raise IndexError


    

In [6]:

    

rankBSnk(5,2,[0,1,0,0,1])


    

    
Out[6]:





3

In [7]:

    

N, K = 5, 5
[rankBSnk(N, K, v) for v in listBSnk(N, K)] == range(binom(N, K))


    

    
Out[7]:





True

In [8]:

    

def unrankBSnk(n, k, r):
    if not 0 <= r < binom(n, k):
        raise IndexError
    if n == 0:
        if k == 0 and r == 0:
            return []
        else:
            raise IndexError
    if k == 0:
        if r == 0:
            return [0]*n
        else:
            raise IndexError
    reccount = binom(n-1, k)
    if r < reccount:
        return [0] + unrankBSnk(n-1, k, r)
    else:
        return [1] + unrankBSnk(n-1, k-1, r - reccount)


    

In [9]:

    

unrankBSnk(5, 2, 3)


    

    
Out[9]:





[0, 1, 0, 0, 1]

In [10]:

    

N, K = 6, 0
[unrankBSnk(N, K, r) for r in range(binom(N, K))] == listBSnk(N, K)


    

    
Out[10]:





True

In [11]:

    

N, K = 100, 50
r = randint(0, binom(N, K))
o = unrankBSnk(N, K, r)
rankBSnk(N, K, o) == r


    

    
Out[11]:





True

In [12]:

    

@cached_function
def binom(n, k):
    if not 0 <= k <= n:
        return 0
    if k == 0:
        return 1
    else:
        return binom(n-1, k) + binom(n-1, k-1)


    

In [13]:

    

[[binom(n, k) for k in range(n+1)] for n in range(11)]


    

    
Out[13]:





[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 7, 1],
 [1, 8, 28, 56, 70, 56, 28, 8, 1],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1],
 [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]]

In [14]:

    

binom(100, 50)


    

    
Out[14]:





100891344545564193334812497256

In [ ]: