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

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
被浏览
62
分享
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+M和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

为了自己生成方式（如果需要），请考虑 itertools.combinations

StJoesy 2019-07-04 16:29:03

谢谢！你指出了我的错误。我尝试使用Pascal矩阵，这是一回事，但效率更高。解决方案仍然很慢（所有n，m> 4000），但是您是正确的，因此我将接受您的解决方案。

StJoesy 2019-07-04 16:29:09

stackoverflow.com/questions/4941753/…

MBo 2019-07-04 16:35:46

该代码执行约2 * k次操作，在普通Python中应该相当快。但是某些模块的内置函数可能在内部使用C代码，并且尽管使用的效率较低，但速度明显更快。

热门帖子

1
内蒙古联通双拨没了 好遗憾 毕竟我这里之前双拨能叠加网速
2
总是感觉到 Apple Silicon 让双系统变得很难办
3
万界星空科技MES管理系统与其他系统的集成
4
使用 clash 上网时应对 dns 泄露的心得
5
facetime 诈骗电话怎么办？
6
大龄码农被裁员，笔记本求推荐
7
北京 5G/4G 游戏延迟稳定性有办法优化吗？
8
Hiddify 不支持在 Google play 中下载，怎么办？
9
iCloud 2T 国区拼车
10
ios,繁简互换

相关问题

1
如何使用python cut方法创建bin，接受一个参数并返回适当的bin？
2
从具有特定条件的列表列表创建字典
3
根据行值选择列，Python，Pandas
4
在数据框中绘制零和一的计数
5
python函数。
6
在两个DataFrame之间执行大量Pandas查找的最佳方法
7
如何获取Pandas数据透视表中的列数和每列的宽度？
8
在Pandas数据框中分组时缺少所需值时显示一列
9
Python隐藏壁虱但显示壁虱标签
10
获取Entry和checkbutton值Tkinter时出现问题

热门github

1
A multi-platform library for OpenGL, OpenGL ES, Vulkan, window and input (翻译：适用于 OpenGL、OpenGL ES、Vulkan、窗口和输入的多平台库)
2
Dev tool that writes scalable apps from scratch while the developer oversees the implementation (翻译：可扩展开发工具的 PoC，该工具从头开始编写整个应用程序，同时开发人员监督实施)
3
shadcn/ui, but for Svelte. ✨ (翻译：shadcn-svelte是shadcn/ui的非官方社区主导的Svelte端口。)
4
The Python Risk Identification Tool for generative AI (PyRIT) is an open access automation framework to empower security professionals and machine learning engineers to proactively find risks in their generative AI systems. (翻译：用于生成式 AI 的 Python 风险识别工具 (PyRIT) 是一个开放式访问自动化框架，使安全专业人员和机器学习工程师能够主动发现其生成式 AI 系统中的风险。)
5
Performance-portable, length-agnostic SIMD with runtime dispatch (翻译：Highway 是一个提供可移植 SIMD/向量内在函数的 C++ 库。)
6
ZK Credo (翻译：ZK信条)
7
OpenCodeInterpreter: Integrating Code Generation with Execution and Refinement (翻译：OpenCodeInterpreter：将代码生成与执行和优化集成)
8
Joplin - the secure note taking and to-do app with synchronisation capabilities for Windows, macOS, Linux, Android and iOS. (翻译：Joplin - 一个开源的笔记和待办事项应用程序，具有Windows，macOS，Linux，Android和iOS的同步功能。)
9
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention. (翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
10
This repository contains System Design resources which are useful while preparing for interviews and learning Distributed Systems (翻译：该存储库包含系统设计资源，在准备面试和学习分布式系统时非常有用)
11
Curso para aprender el lenguaje de programación Python desde cero y para principiantes. 75 clases, 37 horas en vídeo, código, proyectos y grupo de chat. Fundamentos, frontend, backend, testing, IA... (翻译：从零开始学习 Python 编程语言的课程，适合初学者)
12
🎓 Path to a free self-taught education in Computer Science! (翻译：🎓计算机科学免费自学教程！)
13
1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java (翻译：十亿行挑战 —— 使用 Java 对文本文件中的 10 亿行数据进行聚合的有趣探索)
14
A collective list of free APIs (翻译：免费 API 的集合列表)
15
📚 Freely available programming books (翻译：📚 免费提供的编程书籍)