温馨提示:本文翻译自stackoverflow.com,查看原文请点击:math - How to calculate efficient way the Permutation of multiset in Python

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

发布于 2020-03-27 11:29:34

我想看看是否使用python中的数学库内置的是“多集置换”。

我知道可以对此进行编程,但目前我还不是Python专家。所以我不能做复杂的方法。这里有人可以吗?

https://zh.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

查看更多

查看更多

提问者
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组合数,二项式系数)的方法来制作这种序列。

从第二个链接(我添加了整数除法)的Python计算nCr值的实现利用了非常优化的算法-它将选择适当步骤的数量减至最少,k并避免了由于同时进行乘法和除法而产生的中间值太大。请注意,对于您的情况,参数为n = N+Mk = 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

为了自己生成方式(如果需要),请考虑 itertools.combinations

发布
问题

分享
好友

手机
浏览

扫码手机浏览