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 !

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))

Edited 5 Years Ago by Gribouillis: n/a

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

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!!

Edited 5 Years Ago by ERINY: n/a

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)

Edited 5 Years Ago by ERINY: n/a

Comments
Do not post three threads of same topic

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.

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)

Edited 5 Years Ago by ERINY: n/a

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))

Edited 5 Years Ago by pyTony: n/a

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.

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))

Edited 5 Years Ago by pyTony: n/a

This article has been dead for over six months. Start a new discussion instead.