Warm tip: This article is reproduced from stackoverflow.com, please click
math python permutation

How to calculate efficient way the Permutation of multiset in Python

发布于 2020-03-27 10:25:25

I'm looking to see if built in with the math library in python is the "Permutation of multiset".

I know that this can be programmed but at the moment I not an expert in python. So I can't do sophisticated way. Is there anybody here who can?

https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets enter image description here

I had a programming challenge (I am not a student but I want to improve myself), but my solution, not enough fast (many test cases mostly timed out). But the problem sounds easy: how many ways exits from top-left to bottom-right in a matrix if you can only step right and down. I do not really want to anybody solve instead of me. I just need some advice. I tried the Pascal matrix which works but slow. I think the "Permutation of multiset" is my solution because there is two types of steps D,R if my matrix MxN (1 ≤ M,N ≤ 106) that means DM-1 and RN-1 steps: n=N+M-2, m1=M-1,m2=N-1

Questioner
StJoesy
Viewed
141
MBo 2019-07-04 12:53

Note that you have wrong initial setting, so you really don't need multiset permutations here.

problem sounds easy: how many ways exits from top-left to bottom-right in a matrix if you can only step right and down

Sequence of elementary moves for NxM matrix contains exactly N down moves and M right moves. There are C(N+M, M) (nCr, combinations number, binomial coefficient) ways to make such sequence.

Python implementation of calculation nCr value from the second link (I added integer division) exploits quite optimal algorithm - it minimizes number of steps choosing proper k and avoids too large intermediate values due to simultaneous multiplication and division. Note that for your case arguments are n = N+M and k = M

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k) # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) // (i + 1)
    return c

For generation of ways themselves (if needed) consider itertools.combinations