问题标签 [decomposition]

我需要一种算法来生成所有可能的正数分区，我想出了一个（作为答案发布），但它是指数时间。

该算法应该返回一个数字可以表示为小于或等于其自身的正数之和的所有可能方式。因此，例如对于数字5，结果将是：

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

所以我的问题是：有没有更有效的算法呢？

编辑：问题的标题是“数字的总和分解”，因为我真的不知道这叫什么。ShreevatsaR 指出它们被称为“分区”，因此我相应地编辑了问题标题。

我正在考虑重构一些非常复杂的代码，这是我正在工作的项目的子系统。我对这段代码的部分检查是它非常复杂，并且包含大量输入、中间值和输出，具体取决于某些核心业务逻辑。

我想重新设计这段代码，使其更易于维护，并且执行得更快，所以一开始我一直在尝试查看每个参数及其相互依赖关系。这导致了一个相当大而复杂的图，我想要一种简化这个图的机制。

不久前，我在一本名为“矩阵设计分解”的关于 SOA 设计的书中遇到了一种技术，它使用输出矩阵以及它们对输入的依赖关系，应用某种形式的矩阵代数，并且可以为这些依赖关系生成业务流程图.

我知道http://www.designdecomposition.com/上有一个可用的网络工具，但是它在您可以拥有的输入/输出依赖项的数量方面受到限制。我曾尝试四处寻找该工具的算法来源（因此我可以尝试自己实现它而不受大小限制），但是我没有运气。

有人知道我可以使用的类似技术吗？目前我什至正在考虑采用依赖矩阵并应用一些遗传算法来看看进化是否可以提出一个更简单的工作流程......

干杯，

艾多斯

编辑：

我将解释动机：

原始代码是为每次用户执行操作（添加、删除或修改项目的某些属性）时计算所有值（大约 60）的系统编写的。这段代码是十多年前写的，而且肯定显示出老化的迹象——其他人在系统中添加了更复杂的计算，现在我们得到了完全不合理的性能（在控制权返回给用户之前最多 2 分钟）。已决定将计算从用户操作中分离出来，并提供一个按钮来“重新计算”这些值。

我的问题出现了，因为有太多的计算正在进行，并且它们基于这样一个假设，即所有必需的数据都可用于计算 - 现在当我尝试重新实现计算时，我一直遇到问题，因为我没有'没有得到这个计算所依赖的不同计算的结果。

这是我想使用矩阵分解方法的地方。MD 方法允许我指定所有输入和输出，并为我提供可用于生成所有输出的“最简单”工作流程。

然后我可以使用这个“工作流程”来了解我需要执行的计算的优先级以获得相同的结果而不会产生任何异常。它还向我展示了我可以并行化计算系统的哪些部分以及分叉点和连接点的位置（我暂时不会担心那部分）。目前我所拥有的只是一个非常大的矩阵，其中显示了许多依赖项，不知道从哪里开始。

我将从我的评论中详细说明：

我不想在实际程序中使用 EA 流程中的解决方案。我想获取依赖矩阵并将其分解为模块，然后我将手动编码——这纯粹是一种设计辅助——我只是对这些模块的输入/输出感兴趣。基本上是这些计算之间复杂的相互依赖关系的表示，以及一些优先级的概念。

假设我有 A 需要 B 和 C。D 需要 A 和 E。F 需要 B、A 和 E，我想有效地将​​问题空间从一组复杂的依赖项划分为一个“工作流程”，我可以检查它以获得更好的理解。一旦我有了这种理解，我就可以提出一个更好的设计/实现，它仍然是人类可读的，所以对于这个例子，我知道我需要计算 A，然后是 C，然后是 D，​​然后是 F。

--

我知道这看起来有点奇怪，如果你看一下我在基于矩阵的分解之前链接到的网站，应该会让你对我的想法有所了解......

就像标题说的那样，我需要为我的正定矩阵A形成cholesky LDL分解（就像普通的cholesky，但是L的一个对角线，D是对角矩阵）。我在 Lapack 中发现只有一个函数可以做到这一点，但它说矩阵 A 必须是三对角矩阵。在一些免费的子程序库（如 lapack）中是否有某种功能可以做到这一点？

我不确定是否可以就该主题提供一般性建议，但请尝试。很难解释我的情况，因为它太复杂而无法解释。这正是问题所在。

我似乎经常偶然发现我尝试设计项目的某些部分的情况，但是要考虑的事情太多了，我无法掌握它。

是否有任何关于如何一次查看我的系统的一般提示或建议？如何找到可以单独设计的较小部分？

我正在研究钣金零件的嵌套，并正在实施 Minkowski Sums 以查找 No Fit Polygons 进行嵌套。问题是我只能给为我计算 Minkowski 和的代码提供凸集作为输入。因此我需要打破一个凹多边形，在凸集上有孔。我也对三角测量持开放态度，但我正在寻找 VC++ (6.0) 上的工作代码。我的时间有点短，因为我的整个代码都准备好了，只是在等待以凸集的形式输入。

如果有经验的人能在这方面帮助我，我将不胜感激。我浏览了其他帖子，但没有找到与此匹配的任何内容。我是机械工程专业的学生，​​对计算机语言非常了解。我所能处理的就是在 VC++ 上编译代码并将其与我现有的代码合并。

我想知道是否有可能（以及如何）将任意 M3 矩阵变换重新表示为一系列更简单的变换（例如平移、缩放、倾斜、旋转）

换句话说：如何从 MComplex 计算 MTranslate、MScale、MRotate、MSkew 矩阵，以便以下等式成立：

MComplex = MTranslate * MScale * MRotate * MSkew（或以其他顺序）

关于Perl编程语言复杂性的一般讨论是什么，比如在讨论其复杂性时应该真正关注什么？

我正在寻找能够分解和分析文件的软件。你知道任何？

我的意思是，给定一个文件，它会告诉我例如：

• 这是一个告诉它是 PNG的幻数，这里开始一个颜色定义，这里是压缩标志，然后是图片数据，等等......

或类似的东西：

• 这是一个 MP3 文件，这是ID3 定义，这是告诉这是联合立体声的标志等等......

我正在寻找一种处理文件的软件，就像Wireshark (Ethereal) 处理网络流量一样。

谢谢！

我正在寻找一种耳分解算法的实现（http://www.ics.uci.edu/~eppstein/junkyard/euler/ear.html）。我检查了networkx，但没有找到。虽然算法布局在我的脑海中模糊不清，但我也希望看到一些参考实现。

我知道 Ulrik Brandes发表了关于线性时间 Eager st-ordering 算法的文章，如果我理解正确，它会导致耳朵分解作为副产品（它甚至包括伪代码，我试图将其作为实现的基础） .

附带问题：第一步可能是图的 st 排序。您知道 st-ordering 算法的任何实现吗？

感谢您的输入。我真的很想通过在 python 中实现耳朵分解算法来为 networkx 做出贡献。

我正在尝试在 C 代码中找到一个程序，该程序将允许我计算方阵的特征值（谱）分解。我特别想找到最高特征值（以及因此它的相关特征值）位于第一列中的代码。

我需要按此顺序输出的原因是因为我正在尝试计算特征向量中心性，因此我只需要计算与最高特征值相关的特征向量。提前致谢！