问题标签 [data-partitioning]

给定一个特定子集的列表，例如

和一个“宇宙”集合

有什么优雅而简单的算法可以用来从 S 中找到由集合组成的 U 的所有可能分区？在此示例中，此类分区包括

等等

相关问题：

• 将数字列表划分为2个相等总和列表的算法
• 将列表分成两部分，它们的总和彼此最接近

假设我有一个列表，其中包含确切的2k元素。现在，我愿意将它分成两部分，其中每个部分的长度为 ，k同时试图使各部分的总和尽可能相等。

快速示例： [3, 4, 4, 1, 2, 1]可能会拆分为[1, 4, 3] and [1, 2, 4]，总和差将是1

现在 - 如果部分可以有任意长度，这是分区问题的变体，我们知道这是弱NP-Complete.

但是关于将列表分成相等部分的限制（假设它总是kand 2k）是否使这个问题可以在多项式时间内解决？任何证明（或证明它仍然存在的证明方案NP）？

我正在尝试生成如下所示的序列集，不是以任何特别的顺序，但这里显示为降序。请注意，每个序列也会下降，因为我对组合感兴趣，而不是排列。我想将每个序列存储为一个数组..或者将序列集存储为一个数组数组更可取，但首先要做的是。

现在我只是专注于生成这些集合，并且我正在尝试以递归方式进行。本质上..这些都是数字序列，当组合将给出一些总数时..在这种情况下为 6。但请注意，当第一个数字为 3 时，随后的数字集只是给出总数的序列集3. 换句话说，6（目标总数）- 3（第一个数字）= 3（总共为 3 的序列集）。因此，应该能够递归地做到这一点。

我尝试编写如下代码（是的，这是我的第一语言，是的，我只学习了大约一个星期，所以我确信这一切都搞砸了）但到目前为止还没有运气。我想如果我可以让递归的核心工作并将所有对象的值放到屏幕上以便我可以逐行跟踪它，我想我可以继续前进，但是在逻辑和语法之间，我'我处于静止状态。

我的逻辑是：

• 定义一个传递代表目标总数的“计数”的方法。
• 创建一个数组，该数组将保存给定的值序列
• 创建一个表示数组中位置的索引（忽略零位置）。
• 定义'delta'并将其初始化为'count'的值，并让它代表数组其余部分的剩余目标总和。（由于最初数组中没有任何内容，因此增量与计数相同。）

然后，循环遍历序列的下一个（第一个）值的可能性，从 1 开始，显然以最大值结束，即“count”本身的值。确定循环中每个值的新增量。

如果 delta 为 0，那么您就完成了，否则确定这个新序列将给出这个新的 delta。可能还需要将新序列附加到当前序列。

我一直在尝试将一个数组划分为两个非空的不相交子集，以使它们的总和相等。

我已经阅读了关于平衡分区问题的 mit 教程，但我的限制不同。我不必考虑整个集合 A（意味着 A1 U A2 不一定会导致 A）。另一个问题是 N 的限制。每个最多有 100 个不同的元素 (<= 100 ) 。
我也阅读 了与我的问题相关的这篇文章，但我什么也得不到。

解释 ：

这是我的示例工作代码

我知道这种方法不能处理不相交的集合，但我无法找出任何其他方法。

我正处于 Dynamic Prog 的学习阶段。我觉得有点困难。有人可以帮我找出我当前算法中的错误吗？

我有一个有序的字符串，需要呈现给用户：

用“B”表示的对象被标记，这样 2 个 B 后面会有一个“~”。

我使用了Howard Hinnant 的组合库，它适用于这个简单的案例。我的测试代码使用位置向量作为通过 for_each_combination 发送的整数。

但是，当我有多个 B 标记时，我不知道该怎么做。

例如，总共 4Bs 需要标记，2 由 '~' 和 2 由 '#'

我写的伪代码是级联的。在第一个 for_each_combination 之后，对于每个结果组合，将每隔一个位置复制到另一个向量并执行另一个 for_each_combination。

考虑到我将使用的组合数量，我希望有更好的方法。

我正在尝试使用 OpenCV 将 cv::Mat 划分为更小的 cv::Mat。我在网上找到了这个方法，但我无法让它工作。我想将一个 cv::Mat 划分为 640 x 480 的块，例如 32 x 32 块，并在我进行时单独对每个块进行操作。

这是我的代码。curr_frame 包含作为 cv::Mat 的总图像。N_per_col 和 N_per_row 分别包含每列和每行的 mb_sz x mb_sz 块的数量。

这编译得很好，但在运行时我在 tmp_img 中得到一个充满 NULL 像素的图像。curr_frame 肯定没问题，我可以用 imshow() 查看。

文档对此不是很清楚，因此将不胜感激任何帮助。

我正在研究一个由 ~10^6 个值组成的数据集，这些值聚集到可变数量的 bin 中。在我的分析过程中，我试图随机化我的聚类，但保持 bin 大小不变。作为一个玩具示例（在伪代码中），这看起来像这样：

所以，我正在寻找一个像“partition.sample”这样的函数，它将采用一个向量（如 seq(1,15)）并从中随机采样，返回一个列表，其中的数据已分区为由“给出的正确 bin 大小”尺寸”。

我一直在尝试自己编写一个这样的函数，因为这项任务似乎并不难。但是，将向量划分为给定的 bin 大小看起来如果“在后台”完成会更快、更有效，这意味着可能不在本机 R 中。所以我想知道我是否只是错过了适当的名称功能，或者是否有人可以指点我周围的智能解决方案:-)

非常感谢您的帮助和时间！:-)

最好的，

莱蒙德

更新：

“no.of.randomizations”是指我运行整个“随机化循环”的实际次数。稍后，这显然会包括比实际采样更多的步骤。

此外，我还对在不替换的情况下进行上述采样的技巧感兴趣。

在此先感谢，非常感谢您的帮助！

我有一个 List 实现的 ArrayList 具有大量索引。我想将它分成单独的 ArrayList。我做了

等等。我不知道这是否是正确的分区方式。你能建议我一种有效的分区方法吗？

[编辑]

我有一个这样的arrayList：

这个列表很长。我想从上面的列表中获取一些小尺寸的子列表。每个列表都将包含不重叠的列表：

[编辑] 请不要混淆它[]是空列表。我想显示列表中的列表数量。

在研究 项目欧拉练习 (#78)时，我了解到为了对数字进行分区，您可以创建一个幂级数。从该系列中，您可以扩展并使用术语系数来获得划分特定数字的方法的数量。

从那里，我创建了这个小函数：

这在相对较小的分区上工作得很好，但是在这个练习中没有。有没有办法通过递归或更快的算法来加快速度？我读过一些地方，使用五边形数字也是一种帮助分区的方法。

现在我不需要返回这个问题的实际数字，但是，检查它是否能被 1000000 整除。

更新：我最终使用了五角数定理。我将尝试使用 Craig Citro 发布的 Hardy-Ramanujan 渐近公式。

我正在开发一个 3D 游戏引擎作为一个项目。我想对场景中的每个三角形/多边形使用空间分区算法来有效地检测碰撞。我只想知道（在我开始编写细节之前）现代计算机游戏中典型的空间分区算法有多快？我有动态对象，所以我想我可能必须每帧重新分区我的场景。这是否可能并且仍能达到合理的帧速率？如果答案可以包含数据（例如 FPS、多边形数量等），将不胜感激。如果那太麻烦了，请告诉我重新分区每一帧是否合理。

任何帮助，将不胜感激。