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
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
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.
stackoverflow.com/questions/4941753/…
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.