0

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 !

5
Contributors
12
Replies
14
Views
5 Years
Discussion Span
Last Post by pyTony
Featured Replies
  • 1

    Easiest is to cheat by caching the results: [CODE]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)) … Read More

  • 1
    WaltP 2,905   5 Years Ago

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

0

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 by Gribouillis: n/a

0

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

0

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 by ERINY: n/a

-1

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 by ERINY: n/a

Comments
Do not post three threads of same topic
0

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.

0
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 by ERINY: n/a

1

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 by pyTony: n/a

0

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.

0

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 by pyTony: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.