math - 如何在Python中计算有效的多集置换方法

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

StJoesy

31
MBo 2019-07-04 12:53

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

`NxM`矩阵的基本移动序列包含精确的`N`向下移动和`M`向右移动。`C(N+M, M)``nCr`组合数，二项式系数）的方法来制作这种序列。

``````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
``````