How to make Pascal's triangle wtih combination ?

[ERINY]

Hi, i'm python beginner.

how to make that only use def, for, list, while ..

def comb(n,r):
if r == 0:
return 1
elif r == n:
return 1
else:
return comb(n-1,r-1) + comb(n-1,r)

this code is very slow....

ah , I have to use recursion .!

please tell me !

[Gribouillis]

There are mathematical formulas for combination

# this is not python code
comb(n, r) = n!/(r! * (n-r)!) = [n*(n-1)*...*(n-r+1)]/[r*(r-1)*...*1]
comb(n,r) = comb(n, n-r)

you can compute this recursively or not.
You could also use the fraction module and compute the product of r terms

# again doesn't work directly in python
(n/r)*((n-1)/(r-1)) * ... * ((n-r+1)/(1))

[ERINY]

um.. i know mathematical formulas for combination..

but ,how to make

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
...
so i write comb(5,3), how can i receive 10

[Gribouillis]

um.. i know mathematical formulas for combination..

You know them, but you don't use them in your code.

[ERINY]

so , how can make combination with recursion ??

def comb(n,r):
    i = [1,1]
    x = 1
    if n == 0:
        return 1
    elif n < r:
        print("Invalid range....!")
    else:
        def pascal(n,r):
            while r >= n:
                i = i.append(i[x-1]+i[x])
                print(i)
                x += 1
        return i[r-1]

it doesn't work! i'am crazing!!

[ERINY]

I have to make combination program,
but i don't know what to do at this point..
now Type Error.. help me please !

def comb(n,r):
    i = [[1],[1,1]]
    t=[]
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        def pascal(n,r):
            for i in range(r+1):
                if i == 0 or i == n:
                    t.append(1)
                else:
                    t.append(i[n-1][r-1]+i[n-1][r])
            i.append(t)
            return i
        return pascal(n,r)

[TrustyTony]

pascal is never called.

[TrustyTony]

If you want to make recusive function, you must first identify the simple case you know, then you make other clause from rule how to produce result for n, when result for n-1 is known using the recursive function call to function itself.

[ERINY]

def comb1(n,r):  #definite
    i = [1,1]   #base
    if n < r :  #nCr condition
        print("n have to bigger than r.")
    elif n < 0 or r < 0:    #nCr condition
        print("input only positive number.")
    elif n==0:  #0Cn = 1
        return 1
    elif n == 1:    #1Cn = 1
        return 1
    else:   #calculate
        p = 2   #base
        def pascal(p,i,n,r):    #for tail recursion
            t = []  #initialization / t stroed list temporarly
            for x in range(p+1):    #x=0 ~ x= p doing
                if x == 0 or x == p:    #nC0 or nCn = 1
                    t.append(1) # add 1 to t
                elif x < n:     
                    t.append(i[p-1][x-1]+i[p-1][x])     #nCr = n-1Cr-1 + n-1Cr
            i = t     #cover t to i
            if p == n:  # Quit condition
                return i[n][r]  #result
            else:
                return pascal(p+1,i,n,r)    #n-k -> n-k+1 -> ... -> n                
        return pascal(p,i,n,r)

[TrustyTony]

Easiest is to cheat by caching the results:

from scipy.misc import comb as c
def comb(n,r):
    if r == 0 or r==n:
        return 1
    elif (n,r) not in comb.cache:
        comb.cache[n-1,r-1] = comb(n-1,r-1)
        comb.cache[n-1, r] = comb(n-1,r)
        comb.cache[n,r] = comb(n-1,r-1) + comb(n-1,r)
    return comb.cache[n,r]
comb.cache = {}

print(comb(5,3))
print(c(5,3))
print(comb(123,21))
print(c(123,21))

[WaltP]

Don't know. You didn't tell us.

[Ezzaral]

3 separate threads for this single question merged. Apologies for some slight discontinuity, but if ERINY hadn't decided to string this out so much it would be more linear.

[TrustyTony]

Simplest result is not to use recursion, but dynamic programming:

def comb(n,r):
    if n < r:
        raise ValueError('n can not be smaller than r')
    r = min(r, n - r)
    if r == 0:
        return 1
    elif (n,r) not in comb.cache:
        a = comb.cache[n-1, r-1] = comb(n-1, r-1)
        b = comb.cache[n-1, r] = comb(n-1, r)
        comb.cache[n, r] = a + b
    return comb.cache[n, r]
comb.cache = {}

def comb_dyn(n, r):
    if n < r:
        raise ValueError('n can not be smaller than r')
    # dynamic programming from basics to higher
    cs = [1]
    # limit necessary length for values
    r = min(r, n - r)
    for _ in range(n):
        cs_new = [1]
        cs_new.extend(a + b for a, b in zip(cs[:r+1], cs[1:r+1]))
        if len(cs_new) <= r: 
            cs_new.extend([1])
        cs = cs_new
        #if len(cs) < 10:
        #    print(cs)
    return cs[r]

print(comb(10, 5))
print(comb_dyn(10, 5))
print(comb(123, 21))
print(comb_dyn(123, 21))
print(comb(123, 123))
print(comb_dyn(123, 123))
print(comb(0, 0))
print(comb_dyn(0, 0))