Function that computes Permutation

e-papa 0 Tallied Votes 701 Views Share

Well just run, the only thing is that this is created using python 3.x. no modules required.

def fact(n):
    """Computes n!"""
    if n==0:
        return 1
    else:
        p=1
        while n!=1:
            p*=n
            n=n-1
        return p
def perm(n,r):
    """computes nPr, input n,r"""
    b=(n-r)
    a=fact(n)
    b=fact(b)
    c=a//b
    return c
#test case
#print(perm(5,1))
#>>>5
e-papa 13 Posting Pro in Training

Great guys in the house, i know you're there how can this be better, please i need your replies.

TrustyTony 888 pyMod Team Colleague Featured Poster

Generally you give solutions in code snippets not do discussions. Of course sometimes some bugs are hiding in the code even you try to debug it well before posting as code snippet solution.

Anyway here another section of my Project Euler utilities, actually the combination code is from wikipedia, it is more efficient not using factorial.

There is also another version with factorial of my own.

The factorial code is using memo list as factorials attribute (functions are objects). So if you call factorial multiple times it calculates only those factorials which are higher than before used:

The binomial coefficient code actually is little different as it returns 1 even if k > n. But it is here without modifications (except name change)

def factorial(n):
    if len(factorial.memo)-1 < n:
        m = len(factorial.memo)-1
        while m<=n:
            m += 1
            factorial.memo.append(m*factorial.memo[-1])
    return factorial.memo[n]
factorial.memo = [1,]
#wikipedia, binomial coefficient
def combinations(n,k):
    if k > n - k: # take advantage of symmetry
        k = n - k
    c = 1
    for i in range(k):
        c = c * (n - i)
        c = c / (i + 1)
    return c
binomial_coefficient = combinations

def binomial(n,k):
    if n > k:
        return int(factorial(n) / (factorial(k)*factorial(n-k)))

#test by assertion
assert binomial(52,5) == combinations(52,5) ==  2598960
TrustyTony 888 pyMod Team Colleague Featured Poster

Sometimes it is good to post your code to get PPS (Post Posting Syndrome). My factorial was bit messy, here the cleaned up one (debug print commented out):

def factorial(n):
    assert n >= 0
    m = len(factorial.memo) - 1
    while m < n:
        m += 1
        #print m,
        factorial.memo.append(m * factorial.memo[-1])
    return factorial.memo[n]
factorial.memo = [1]
e-papa commented: Explain more bro. +1
Lardmeister 461 Posting Virtuoso

Permutations of words are actually fun:

# permutations using Python module iterools
# needs Python26 or higher
# itertools.permutations(iterable[, r]) is a generator/iterator

import itertools as it

word = "rats"
# default is len(word)
for p in it.permutations(word):
    # join tuple p to form a string
    print( p, ''.join(p) )

""" my output --->
(('r', 'a', 't', 's'), 'rats')
(('r', 'a', 's', 't'), 'rast')
(('r', 't', 'a', 's'), 'rtas')
(('r', 't', 's', 'a'), 'rtsa')
(('r', 's', 'a', 't'), 'rsat')
(('r', 's', 't', 'a'), 'rsta')
(('a', 'r', 't', 's'), 'arts')
(('a', 'r', 's', 't'), 'arst')
(('a', 't', 'r', 's'), 'atrs')
(('a', 't', 's', 'r'), 'atsr')
(('a', 's', 'r', 't'), 'asrt')
(('a', 's', 't', 'r'), 'astr')
(('t', 'r', 'a', 's'), 'tras')
(('t', 'r', 's', 'a'), 'trsa')
(('t', 'a', 'r', 's'), 'tars')
(('t', 'a', 's', 'r'), 'tasr')
(('t', 's', 'r', 'a'), 'tsra')
(('t', 's', 'a', 'r'), 'tsar')
(('s', 'r', 'a', 't'), 'srat')
(('s', 'r', 't', 'a'), 'srta')
(('s', 'a', 'r', 't'), 'sart')
(('s', 'a', 't', 'r'), 'satr')
(('s', 't', 'r', 'a'), 'stra')
(('s', 't', 'a', 'r'), 'star')
"""

word = "bush"
for p in it.permutations(word, 3):
    # join tuple p to form a string
    print( p, ''.join(p) )

""" my output --->
(('b', 'u', 's'), 'bus')
(('b', 'u', 'h'), 'buh')
(('b', 's', 'u'), 'bsu')
(('b', 's', 'h'), 'bsh')
(('b', 'h', 'u'), 'bhu')
(('b', 'h', 's'), 'bhs')
(('u', 'b', 's'), 'ubs')
(('u', 'b', 'h'), 'ubh')
(('u', 's', 'b'), 'usb')
(('u', 's', 'h'), 'ush')
(('u', 'h', 'b'), 'uhb')
(('u', 'h', 's'), 'uhs')
(('s', 'b', 'u'), 'sbu')
(('s', 'b', 'h'), 'sbh')
(('s', 'u', 'b'), 'sub')
(('s', 'u', 'h'), 'suh')
(('s', 'h', 'b'), 'shb')
(('s', 'h', 'u'), 'shu')
(('h', 'b', 'u'), 'hbu')
(('h', 'b', 's'), 'hbs')
(('h', 'u', 'b'), 'hub')
(('h', 'u', 's'), 'hus')
(('h', 's', 'b'), 'hsb')
(('h', 's', 'u'), 'hsu')
"""
e-papa 13 Posting Pro in Training

Generally you give solutions in code snippets not do discussions. Of course sometimes some bugs are hiding in the code even you try to debug it well before posting as code snippet solution.

Anyway here another section of my Project Euler utilities, actually the combination code is from wikipedia, it is more efficient not using factorial.

There is also another version with factorial of my own.

The factorial code is using memo list as factorials attribute (functions are objects). So if you call factorial multiple times it calculates only those factorials which are higher than before used:

The binomial coefficient code actually is little different as it returns 1 even if k > n. But it is here without modifications (except name change)

def factorial(n):
    if len(factorial.memo)-1 < n:
        m = len(factorial.memo)-1
        while m<=n:
            m += 1
            factorial.memo.append(m*factorial.memo[-1])
    return factorial.memo[n]
factorial.memo = [1,]
#wikipedia, binomial coefficient
def combinations(n,k):
    if k > n - k: # take advantage of symmetry
        k = n - k
    c = 1
    for i in range(k):
        c = c * (n - i)
        c = c / (i + 1)
    return c
binomial_coefficient = combinations

def binomial(n,k):
    if n > k:
        return int(factorial(n) / (factorial(k)*factorial(n-k)))

#test by assertion
assert binomial(52,5) == combinations(52,5) ==  2598960

Please can you explain the codes above, i see assert, memo, and stuffs please will really like if you can expatiate, i know there more to be done.

e-papa 13 Posting Pro in Training

Permutations of words are actually fun:

# permutations using Python module iterools
# needs Python26 or higher
# itertools.permutations(iterable[, r]) is a generator/iterator

import itertools as it

word = "rats"
# default is len(word)
for p in it.permutations(word):
    # join tuple p to form a string
    print( p, ''.join(p) )

""" my output --->
(('r', 'a', 't', 's'), 'rats')
(('r', 'a', 's', 't'), 'rast')
(('r', 't', 'a', 's'), 'rtas')
(('r', 't', 's', 'a'), 'rtsa')
(('r', 's', 'a', 't'), 'rsat')
(('r', 's', 't', 'a'), 'rsta')
(('a', 'r', 't', 's'), 'arts')
(('a', 'r', 's', 't'), 'arst')
(('a', 't', 'r', 's'), 'atrs')
(('a', 't', 's', 'r'), 'atsr')
(('a', 's', 'r', 't'), 'asrt')
(('a', 's', 't', 'r'), 'astr')
(('t', 'r', 'a', 's'), 'tras')
(('t', 'r', 's', 'a'), 'trsa')
(('t', 'a', 'r', 's'), 'tars')
(('t', 'a', 's', 'r'), 'tasr')
(('t', 's', 'r', 'a'), 'tsra')
(('t', 's', 'a', 'r'), 'tsar')
(('s', 'r', 'a', 't'), 'srat')
(('s', 'r', 't', 'a'), 'srta')
(('s', 'a', 'r', 't'), 'sart')
(('s', 'a', 't', 'r'), 'satr')
(('s', 't', 'r', 'a'), 'stra')
(('s', 't', 'a', 'r'), 'star')
"""

word = "bush"
for p in it.permutations(word, 3):
    # join tuple p to form a string
    print( p, ''.join(p) )

""" my output --->
(('b', 'u', 's'), 'bus')
(('b', 'u', 'h'), 'buh')
(('b', 's', 'u'), 'bsu')
(('b', 's', 'h'), 'bsh')
(('b', 'h', 'u'), 'bhu')
(('b', 'h', 's'), 'bhs')
(('u', 'b', 's'), 'ubs')
(('u', 'b', 'h'), 'ubh')
(('u', 's', 'b'), 'usb')
(('u', 's', 'h'), 'ush')
(('u', 'h', 'b'), 'uhb')
(('u', 'h', 's'), 'uhs')
(('s', 'b', 'u'), 'sbu')
(('s', 'b', 'h'), 'sbh')
(('s', 'u', 'b'), 'sub')
(('s', 'u', 'h'), 'suh')
(('s', 'h', 'b'), 'shb')
(('s', 'h', 'u'), 'shu')
(('h', 'b', 'u'), 'hbu')
(('h', 'b', 's'), 'hbs')
(('h', 'u', 'b'), 'hub')
(('h', 'u', 's'), 'hus')
(('h', 's', 'b'), 'hsb')
(('h', 's', 'u'), 'hsu')
"""

Thanks for showing me something new, but how can i get the itertools, and then what are the things it does, is there a way i can get docs on it, please i really want to leard more.Is it built in with python.

e-papa 13 Posting Pro in Training

Thanks guys please let the ideas keep coming, we are going places.

vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

Thanks for showing me something new, but how can i get the itertools, and then what are the things it does, is there a way i can get docs on it, please i really want to leard more.Is it built in with python.

The Python module itertools is part of your normal Python installation. Simply see the Python documents that should have installed too. If you installed Python on Windows with the ms-installer python-3.2.msi, then you should find the documentation in directory C:\Python32\Doc as file python32.chm. Just double-click on it and use the index.

TrustyTony 888 pyMod Team Colleague Featured Poster

Explanations of memo version of factorial

def factorial(n):
    # causing assert failure if negative n given
    assert n >= 0
    # finding the current maximum index of memo list keeping calculated  factorials
    m = len(factorial.memo) - 1
    while m < n:
        # if we enter here, we have some needed factorials missing, continue to build
        # the list of factorials until the requested n
        m += 1
        # print(m, end=', ') # python3 version of the debug print to visualize memoization
        # we will memorize each new value of factorial in list memo 
        # which is property of function factorial 
        factorial.memo.append(m * factorial.memo[-1]) 
    # give value ready in memo list
    return factorial.memo[n]
# in the beginning we only know that 0! = 1
factorial.memo = [1]
e-papa 13 Posting Pro in Training

Okay will try and read up.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.