问题标签 [data-partitioning]

给定 n（比如 3 个人）和 s（比如 100$），我们想在 n 个人中划分 s。

所以我们需要总和为 s 的所有可能的 n 元组

我的 Scala 代码如下：

这适用于 n 的小值。（n=1、2、3 或 4）。

超过 n=4，需要很长时间，实际上无法使用。

我正在寻找使用惰性评估/ Stream 来修改我的代码的方法。

我的要求：必须为 n 最多 10 工作。

警告：问题变得非常大非常快。我从 Matlab 得到的结果——

我正在寻找一种有效的方法来计算异或为零的整数分区数： F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }

对于 n 和 c 的小值，很容易运行嵌套循环来计算这些值。但是对于较大的值，它是不可处理的。我想获得一个封闭的形式或至少一个允许动态编程的递归公式..

如何将 48 件物品分配给 3 位继承人中的每一位，以使每个人的价值相等或几乎相等？

这是一种划分问题的形式，是 NP 完全的（或类似的），因此不可能用 48 个项目完美回答。我正在寻找一种实用且公认的近似算法来执行此操作。这是许多人在解决遗嘱和遗产时面临的问题。答案一定在某处！答案可能是计算机脚本，也可能只是手动方法。

“普遍接受”的启发式就足够了。带着我的程序员帽子，我寻求一个近乎完美的解决方案。带着我的法律执行人帽子，我寻求一些普遍接受或法律先例“足够好”的东西。

编程语言环境：LibreOffice 中的 Visual Basic 其他研究：Wikipedia、MathIsFun、CodingTheWheel

我想以特定方式为集合生成分区：我需要在生成这些分区的过程中过滤掉所有大小不为 N 的分区。一般的解决方案是“生成集合（不是幂集）的所有“唯一”子集”。

对于S具有以下子集的集合：

以及以下“独特”元素：

使用参数运行的函数/方法的结果N = 2应该是：

虽然以下分区应通过函数/方法过滤掉：

底层数据结构并不重要，可以是数组、集合或其他。

原因：在获得所有分区的完整集之前，我需要过滤掉一些分区，因为生成所有分区的函数/方法的计算量相当大。

根据“生成集合的分区”，可能的分区数量可能很大：23 个元素为 44152005855084346。我的数据是起始集中的 50-300 个元素，所以在将它们保存在任何地方之前，我肯定需要过滤掉大小不等于 N 的分区。

注意：这个问题是基于对我之前类似问题的重新思考。

我想知道 Erlang 的sofs:partition是否与 Wikipedia's page about Set partitions中描述的相同。

如果是这样，我怎样才能得到以下结果？

给定一个数据结构（一组集合或列表列表）：

其中包含以下独特元素：

使用参数运行函数的结果N = 2应该是：

而在执行过程中需要过滤掉以下分区sofs:partition：

我可以用 sofs:partition 做到这一点吗？length(Partition) =/= N如果是，我可以迭代地做，在执行过程中扔掉分区吗？是否有可能以某种方式重新定义sofs:partition函数以引入 N 参数？

我有一个名单。

我想将此列表划分为指定大小的组。所有组应等于或小于指定大小，各组之间的组大小应尽可能相等，并尽可能接近指定大小。

什么算法（如果可能，请使用 Java 类伪代码！）确定最合适的组大小？

例如：

列表包含 13 个名称 - 最大团队规模 3。输出（组规模）：3、3、3、2、2

列表包含 13 个名称 - 最大团队规模 4。输出：4、3、3、3

列表包含 31 个名称 - 最大团队规模 5。输出：5、5、5、4、4、4、4

列表包含 31 个名称 - 最大团队规模 6。输出：6、5、5、5、5、5

列表包含 31 个名称 - 最大团队规模 10。输出：8、8、8、7

我有一套S。它包含N子集（其中又包含一些不同长度的子子集）：

我还有一个L包含在集合中的“独特”元素列表S：

我需要从每个子集的每个子集之间找到所有可能的组合，以便每个结果组合都具有 list 中的一个元素L，但该元素的出现次数为任意数量[*]（它是通配符元素）。

因此，使用上述集合的所需函数的结果S应该是（不是 100% 准确）：

所以，基本上我需要一个执行以下操作的算法：

1. 从子集中取一个子集1，
2. 2从维护到目前为止获得的“唯一”元素列表的子集中添加一个子集（如果子集包含该*元素，则跳过对“唯一”列表的检查）；
3. 重复2直到N达到。

换句话说，我需要生成所有可能的“链”（它是对、 ifN == 2和三元组 if N==3），但是每个“链”应该只包含列表中的一个元素，L除了可以在每个生成的通配符元素*中出现多次链。

我知道如何做到这一点N == 2（这是一个简单的对生成），但我不知道如何增强算法以使用N.

也许第二种斯特林数在这里会有所帮助，但我不知道如何应用它们来获得所需的结果。

注意：这里使用的数据结构类型对我来说并不重要。

注意：这个问题是从我之前的类似问题中衍生出来的。

由于正常分区返回一个索引 j ，使得索引 i <= j 的每个元素都小于选择的枢轴，并且索引 m > j 的每个元素都大于枢轴，因此不能保证 j 是枢轴。是否有可能创建另一个准确返回新枢轴位置的就地分区算法？最初，我坚持将选择的枢轴移动到最后一个位置，但这并没有导致最佳解决方案。

几个星期以来，我一直在尝试自学 Prolog。现在，我正在尝试使用partition/3我想要使用的谓词从几个较小的整数中找到所有方法来生成一个大整数：

从而找到从 1、2 和 3 生成 4 的所有方法。像 [1, 2, 1] 和 [2, 1, 1] 这样的重复解决方案很好，但可能不难避免。这是我现在拥有的：

这个想法是 N 最终会变为零，并且得到它的减法将作为列表放在第三个参数中。第三和第四条规则只对正整数起作用，第二条规则说不要用完输入，第一条规则表示当 N 达到零时分区有效。问题是，我只得到：

第一条和第二条规则对我来说很有意义，第三条和第四条似乎有问题，但我找不到它们有什么特别的问题。我认为OT当 M 变为零时，输出尾部可能不会被实例化，但第一条规则会解决这个问题。还是对 Prolog 的工作方式存在一些根本性的误解（这对我来说似乎经常发生）？

另外，N =< 0, fail;零件是多余的吗？它们似乎是多余的，但在我得到一些有用的东西之前我不能确定。

编辑：我正在使用 GNU Prolog。

我有 N 个字符串，我想将字典分成 M 个均匀大小的桶（+/- 1 个字符串）。此外，N>>M。

直接的方法是对所有字符串进行排序并将结果列表拆分为 M 个桶。

我想通过在完整列表可用之前将创建的每个字符串路由到存储桶来近似这一点。

是否有一种快速且 Pythonic 的方式将字符串分配给存储桶？我本质上是在寻找整数模运算符的字符串等效项。也许是保留字典顺序的哈希？这甚至可能吗？