问题标签 [data-partitioning]

我正在寻找有关“产品分区”的信息（我不知道正式名称）
在“经典”分区中，我们搜索正整数的分解作为总和：

我想找到所有的分解作为产品：

我有一个递归解决方案，但效率不够。
非常感谢您提供任何信息。

Philippe
PS
这是我的解决方案（C#）：

---------------------------------------------- （7月10日）
尽管此处发布了各种答案，但我仍然遇到性能问题。
如果素数是 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }，并且我将我的版本应用于素数的前 N ​​个元素的乘积，我得到的结果是：

我相信有更好的。
如果这个功能已经被研究过并且我可以在哪里找到信息，没有人回答我。
我在互联网上尝试了几次搜索都是徒劳的......

再次感谢你的帮助。
菲利普

我尝试在 Web 和我的算法书中搜索Lomuto 的QSort 分区的特定解决方案是否稳定（我知道 Hoare 的版本不稳定）但我没有找到准确的答案。
所以我试着做同样的例子，它看起来很稳定。但我没有演示。你可以帮帮我吗？如果它不稳定，你能给我找一个输入的例子吗？

我想将 C# 中的序列拆分为使用 LINQ 的序列序列。我做了一些调查，我发现的最接近的 SO 文章稍微相关的是this。

但是，这个问题只问如何根据常数值对原始序列进行分区。我想根据操作对我的序列进行分区。

具体来说，我有一个包含小数属性的对象列表。

假设我有一个 的序列ExampleClass，对应的值序列TheValue是：

我想将原始序列划分为一个类似的IEnumerable<IEnumerable<ExampleClass>>值TheValue：

我只是不知道如何实施。所以，你能帮忙吗？

我现在有一个非常丑陋的解决方案，但有一种“感觉”，即 LINQ 会增加我的代码的优雅度。

一个简单的快速排序将花费 O(n^2) 时间来对不包含唯一键的数组进行排序，因为所有键都将在枢轴值之前或之后进行分区。有一些方法可以处理重复的键（例如Quicksort is Optimal中描述的一种）。建议的解决方案仅适用于 Hoare 分区，但我已经实现了 Lomuto 分区。为了处理重复键，我交替将重复项移动到枢轴左侧和将重复项移动到枢轴右侧。该算法的工作原理如下：

是否有更好（更有效）的方法来处理重复键？

编辑：我的代码（如图所示）要求 compareTo 与 equals 一致（即使认为这不是必需的）

在 Introduction to Algorithms 一书中，Quicksort 一章中描述的快速排序算法没有使用 Hoare-Partitioning。

谁能告诉我这种方法相对于流行的 hoare 分区的优势。还是只是作者的选择问题？

我通过 TCP 收到以下消息：

但是当我试图分区时

我得到以下数组：

('{\x00\x00\x00"\x00\x00\x00m\x00\x00\x00e\x00\x00\x00s\x00\x00\x00s\x00\x00\x00a\x00\x00\x00g\x00\x00 \x00e\x00\x00\x00"\x00\x00\x00:\x00\x00\x00\x00\x00\x00"\x00\x00\x00# \x00\x00\x00B\x00\x00\x00E\x00 \x00\x00G\x00\x00\x00I\x00\x00\x00N\x00\x00\x00;\x00\x00 \x00A\x00\x00\x00l\x00\x00\x00l\x00\x00\x00;\x00 \x00\x000\x00\x00\x00;\x00\x00\x001\x00\x00\x00;\x00\x00\x000\x00\x00\x00;\x00\x00\x001\x00\x00\x003\ x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006\x00\x00\x00.\x00\x00\x007\x00\x00\x004\ x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00\x005\x00\x00\x00:\x00\x00\x003\x00\x00\x000\x00\x00\x000\ x00\x00\x000\x00\x00\x000\x00\x00\x00;\x00\x00\x00#\x00\x00\x00E\x00\x00\x00N\x00\x00\x00D\x00\x00\x00" \x00\x00\x00,\x00\x00\x00\x00\x00\x00"\x00\x00\x00c\x00\x00\x00l\x00\x00\x00i\x00\x00\x00e\x00\x00\x00n\x00\x00\x00t\x00\x00\x00"\x00\x00\x00: \x00\x00\x00 \x00\x00\x00"\x00\x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000 \x00\x00\x006 \x00\x00\x00.\x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00\x005 \x00\x00\x00"\x00\x00\x00,\x00\x00\x00\x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00\x00\x00p\x00\x00\ x00e\x00\x00\x00"\x00\x00\x00:\x00\x00\x00\x00\x00\x002\x00\x00\x000\x00\x00\x000\x00\x00\x005\x00\x00\ x00}\x00\x00\x00<\x00\x00\x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{“消息”：“开始”，“客户端”：“134.106.74.21”，“类型”：1009}'，''，''）\x00\x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006\x00\x00\x00。 \x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00\x005\x00\x00\x00"\x00\x00\x00 ,\x00\x00\x00\x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00\x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\ x00:\x00\x00\x00\x00\x00\x002\x00\x00\x000\x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00 \x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{“消息”：“开始”，“客户端”：“134.106.74.21”，“类型”： 1009}', '', '')\x00\x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006\x00\x00\x00。 \x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00\x005\x00\x00\x00"\x00\x00\x00 ,\x00\x00\x00\x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00\x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\ x00:\x00\x00\x00\x00\x00\x002\x00\x00\x000\x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00 \x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{“消息”：“开始”，“客户端”：“134.106.74.21”，“类型”： 1009}', '', '')\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\x00 :\x00\x00\x00\x00\x00\x002\x00\x00\x000\x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00\ x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{“消息”：“开始”，“客户端”：“134.106.74.21”，“类型”：1009 }', '', '')\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\x00 :\x00\x00\x00\x00\x00\x002\x00\x00\x000\x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00\ x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{“消息”：“开始”，“客户端”：“134.106.74.21”，“类型”：1009 }', '', '')

更新

当我尝试添加两个字符串时出现了问题。

我很难将带有 Hoare 分区的 QuickSort 翻译成 C 代码，并且找不到原因。我正在使用的代码如下所示：

另外，我真的不明白为什么HoarePartition有效。有人可以解释它为什么有效，或者至少将我链接到一篇有效的文章吗？

我已经看到了分区算法的逐步工作，但我对它没有直观的感觉。在我的代码中，它甚至似乎都不起作用。例如，给定数组

它将使用枢轴 13，但最终使用数组

并将返回j哪个是a[j] = 11. 我认为从该点开始并向前的数组应该具有都大于枢轴的值，但这里不是这样，因为 11 < 13。

这是 Hoare 分区的伪代码（来自 CLRS，第二版），以防万一：

谢谢！

编辑：

这个问题的正确 C 代码最终将是：

我正在尝试根据谓词列表对地图进行多分区。

我编写了以下函数来做到这一点：

scala 编译器（我正在运行 2.9.1）在指定位置失败，出现“类型不匹配；找到 (A,B) => Boolean，需要：(A,B) => Boolean”。

有没有人见过这样的东西？知道如何解决吗？

谢谢，

LP

是否存在不依赖于数组中存在的枢轴元素的就地分区算法（在快速排序实现中使用的那种）？

换句话说，数组元素必须按以下顺序排列：

• 小于枢轴的元素（如果有）
• 等于枢轴的元素（如果有）
• 大于枢轴的元素（如果有）

如果它恰好出现在数组中，它仍然必须返回枢轴元素的索引（排序后），否则返回一个特殊值；这可能是索引的补码，可以在其中插入元素以保持顺序（如 Java 标准二进制搜索函数的返回值。）

我所看到的实现要求将枢轴元素的索引作为参数给出（或始终位于数组的开头）。不幸的是，我事先不知道枢轴是否存在于数组中（或者它在哪里在数组中。）

编辑（回复meriton的评论）：我们也可以假设以下条件之一为真：

• 数组长度 < 2，或
• 至少一个元素是<= pivot ，至少一个元素是>= pivot。

数组中可能存在重复值（包括枢轴值的重复值。）

我定义了一个递归函数，它接受一个数字 ,n并返回list与该数字相加的数字列表（分区）：

我想知道如何让函数返回number的分区数n。

例如，P(6)将返回10.