How to calculate efficient way the Permutation of multiset in Python

Question

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

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

https://docs.sympy.org/0.7.6/modules/utilities/iterables.html#sympy.utilities.iterables.multiset_permutations — hiro protagonist, Jul 03 '19 at 14:50

MBo · Accepted Answer · 2019-07-04T04:53:03.010

1

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

edited Jul 04 '19 at 04:53

answered Jul 04 '19 at 04:47

MBo

77,366
5
53
86

Thank you! You pointed to my mistake. I tried with Pascal matrix and this is the same thing, but more efficient. The solution this still slow (all n,m > 4000), but you are right, so I going to accept your solution. – StJoesy Jul 04 '19 at 08:29
https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python – StJoesy Jul 04 '19 at 08:29
This code makes about 2*k operations and should be rather fast in plain Python. But in-built functions from some modules might use C code internally and be significally faster despite of using less effective general approach. – MBo Jul 04 '19 at 08:35

Alain T. · Answer 2 · 2019-07-03T15:25:18.587

You can use the permutations() function from itertools to get all permutations and a set to skip over repetitions.

from itertools import permutations

multiset = "MISSISSIPPI"
perms = iter(p for s in [set()] for p in permutations(multiset) if p not in s and not s.add(p))

count = 0
for p in perms:
    count += 1
print(count) # 34650

If you only need to get the count, you can implement the formula (with a little help from math and collections):

from collections import Counter
from math import factorial

def multisetPermutations(A):
    result = factorial(len(A))
    for m in Counter(A).values():
        result = result // factorial(m)
    return result

print(multisetPermutations("MISSISSIPPI")) # 34650

How to calculate efficient way the Permutation of multiset in Python

2 Answers2