Function that computes Permutation

e-papa 0 769 Views

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

Dani AI

Generated

The original perm implementation works but has three common drawbacks: no input validation, unnecessary work computing full factorials when only the top r factors are needed, and potential inefficiency for larger n. Below is a compact, robust alternative that computes nPr in O(r) time by multiplying the descending r terms (no repeated factorial work). This keeps intermediate values small and is easy to reason about.

def nPr(n, r):
    """Return P(n, r) as an integer for integers n >= 0 and 0 <= r <= n.
    Raises TypeError for non-integers and ValueError for negative values.
    Returns 0 if r > n (change to raise if a strict error is preferred).
    """
    if not isinstance(n, int) or not isinstance(r, int):
        raise TypeError("n and r must be integers")
    if n < 0 or r < 0:
        raise ValueError("n and r must be non-negative")
    if r > n:
        return 0
    p = 1
    for k in range(n, n - r, -1):
        p *= k
    return p

Notes and troubleshooting:

  • This approach is exactly what avoids huge unnecessary factorials; for repeated factorial queries, the memoization idea described by is still useful.
  • If only the count is needed and the Python environment exposes a standard helper (e.g., math.perm), prefer that for clarity; if actual permutation lists are required, use itertools.permutations as shown by and confirmed by .
  • Watch types: avoid using float division (/) in combinatorics code — integer arithmetic keeps results exact.
  • Test edge cases: r == 0 should produce 1, r == n produces n!, negative inputs should raise, and decide whether r > n returns 0 or is an error based on the intended semantics.
Member Avatar for e-papa
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.

Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

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
Edited by TrustyTony because: n/a
Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

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]
Edited by TrustyTony because: n/a
e-papa commented: Explain more bro. +1
Member Avatar for Lardmeister
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')
"""
Member Avatar for e-papa
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.

Member Avatar for e-papa
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.

Member Avatar for e-papa
e-papa 13 Posting Pro in Training

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

Member Avatar for vegaseat
vegaseat 1,735 DaniWeb's Hypocrite

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.

Edited by vegaseat because: n/a
Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

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]
Edited by TrustyTony because: n/a
Member Avatar for e-papa
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.

Edit Preview