问题标签 [partition-problem]

我在 Postgres 中有一张大桌子。

表名是bigtable，列是：

我已经对 category_id 的模 10 和 capture_time 列的日期部分的表进行了分区。

分区表如下所示：

当我在 where 子句中使用 category_id 和 capture_time 运行查询时，分区没有按预期修剪。

但是，如果我在 where 子句中添加精确的模标准 ( category_id%10=0)，它会完美运行

有什么方法可以使分区修剪正常工作，而不必在每个查询中添加模条件？

从n的所有分区集合中随机选择的整数分区的共轭也是均匀随机样本吗？我的结果表明是的，这是令人鼓舞的，因为它可以快速生成长度为 s 的 n 的随机分区，但我无法解释为什么应该或不应该这样做。

顺便说一句，我的结果基于 1.) 为特定长度 (s) 的小 n (<70) 生成所有分区 2.) 将每个分区的方差计算为宏状态描述符和 3.) 比较内核整个可行集（长度为 s 的 n 的所有分区）与小随机样本（即 <500 个随机生成的长度匹配 s 或共轭长度匹配 s 的 n 分区）的方差的密度曲线。随机样本的核密度曲线与整个可行集的曲线非常匹配（即所有匹配的 n 个分区）。这直观地说明了随机样本（其中大多数是共轭分区）捕获了基于 n 和 s 的可行集的分区之间的方差分布。我只是无法解释为什么它应该像看起来那样工作；

注意：产生随机样本的许多其他程序会产生明显有偏差的样本（即形状不同且高度不重叠的核密度曲线）。

相关问题：

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

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

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

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

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

所以假设我有一个这样的数组：

有没有一种方便的方法可以将数组分区成这样的东西？

我查看了类似的问题，但大多数人建议使用 k-means 来聚类点，例如scipy，对于像我这样的初学者来说使用起来非常混乱。另外我认为 k-means 更适合二维或更多维聚类，对吧？有什么方法可以根据数字将 N 个数字的数组划分为多个分区/聚类？

有些人还建议进行严格的范围划分，但它并不总是按预期呈现结果

有一个等式：1a + 2b + 3c + 4d ... + 9i = 9

约束：1 <= a + b + c + ... + i <= 10 ⁴

其中a,b,..,i是非负整数，每个整数都有一个特定的范围。

例如：1 <= a <= 5、2 <= b <= 3等等。

我需要找出这些变量的不同值集的数量，或者简单地说，解决该方程的方法的数量。

有一种递归方法可以解决这个问题，但这很慢。在给定的约束下，我无法想出一种有效解决此问题的方法。

这就是问题：

您有两个长度相等的数组 A 和 B。您必须将它们分成两组 P 和 Q，这样：（1）它们的差异最小化。(2) 如果 A[i] 进入 P 或 Q 之一， B[i] 应该进入另一个。

这是实际问题的链接：http: //opc.iarcs.org.in/index.php/problems/EQGIFTS

这是我的逻辑（解决实际问题）：

如果输入为：abcdefg，则值列表和 a,b,c,d,e,f 的索引分别为 0,1,2,3,4,5

如果 t 是 a,b,c,d,e,f,g 的索引，则程序检查 t 和 i 使得： [t] 处的值 > [ti] 处的值，从 t = 5 开始，并且 i = 1，并将 i 的值增加 1 并将 t 的值减少 1。

一旦找到匹配项，它就会交换两个索引的值并对从 [t-1] 开始的值进行排序。结果值列表是输出。

我不知道这个算法有什么问题，但它对所有测试用例产生了错误的答案。我知道它可以使用动态编程来解决，并且它是分区问题的一种变体。但我不知道如何改变分区算法来解决这个问题。

我在 matlab 中有一个 MinCUT 算法。这是一个功能！我如何从我的邮件文件中调用它！我必须定义所有变量吗？还是我必须只定义输入？

如何找到整数列表的所有分区？大多数情况下，我需要使用递归的算法，因为我将在 SML 中实现它。我只需要算法，我会自己做编码部分。我错误地编写了查找子集的代码，我没有太多时间来做这个

SML 有点类似于帕斯卡，所以你会掌握我要在阶乘中编写的格式，例如这个有趣的 fuc x = if x<0 then 0 else if x=1 then 1 else x*(fac x-1)

提前致谢

我想实现平衡分区问题并使用反向指针获取子集的元素。

我有一个关于反向指针的问题：

在麻省理工学院的动态编程练习题 Nr 的帮助下。7和这个示例代码，我设法在处理中获得了一个工作程序（因为我是一个编程新手......）。

现在我希望能够获得两个子集的元素。

在 MIT Video 中解释说，这可以“使用维护反向指针的标准技巧”来实现。

有谁知道如何做到这一点？

我一直在解决一些算法编程问题，并且有一个问题。问题与此问题中引用的问题相同：USACO: Subsets (Inefficient)

我能够编写一些对于高 N 来说太慢的（非动态）解决方案。不得不作弊并在线查找一些解决方案。事实证明，快速算法非常简单，但即使知道答案，我仍然看不出如何从问题中得到答案。我可以看到等和子集形成的模式，但我看不到这些模式与算法解决方案之间的联系。

问题（上面的链接）是：

给定一组从 1 到 N (1 <= N <= 39) 的连续整数，有多少种方法可以将该集合划分为两个总和相同的子集？例如，{1,2,3} 可以以一种方式分区：{1,2} {3}。

对于较大的集合，答案要么是 0（当 N*(N+1)/2 为奇数时），要么由以下简单算法给出：

再一次，我可以看到算法是如何工作的，我什至插入了打印语句，所以我可以“观察”它是如何工作的。我只是看不出算法的操作如何与生成两组分区的不同方式的模式联系起来。

链接问题中的回答可能是相关的，但我也无法连接它是如何工作的：“这与在多项式 (x^1+1/x)(x) 中找到系数 x^0 项相同^2+1/x^2)...(x^n+1/x^n)..."

任何人都可以为我澄清联系，或者向我指出一些解释这个特定问题的参考资料吗？谢谢。