问题标签 [data-partitioning]

集合 {1,2,3,4} 可以构成多少个具有恰好两个部分的不同分区？此列表中有 4 个元素需要分成 2 个部分。我把这些写出来，总共有 7 种不同的可能性：

1. {{1},{2,3,4}}
2. {{2},{1,3,4}}
3. {{3},{1,2,4}}
4. {{4},{1,2,3}}
5. {{1,2},{3,4}}
6. {{1,3},{2,4}}
7. {{1,4},{2,3}}

现在我必须为集合 {1,2,3,...,100} 回答同样的问题。此列表中有 100 个元素需要分成 2 个部分。我知道分区的一部分的最大尺寸是 50（即 100/2），最小的是 1（所以一部分有 1 个数字，另一部分有 99）。如何在不写出每个可能组合的无关列表的情况下确定两个部分的分区有多少种不同的可能性？答案可以简化为阶乘（比如 12！）吗？
有没有一个通用公式可以用来找出有多少个恰好有 n 个部分的不同分区可以由一个带有 k 元素的集合组成？

我目前在业余时间学习算法，但在学习第 3 章 select() 算法时有以下问题。

我知道如果我使用从 A 到 n 个数字的数组，我可以使用 select() 算法来查找中位数（第 n/2 个最小数字）。

1）但这是我难以理解的一点。A = [3, 7, 5, 1, 4, 2, 6, 2]。假设这是数组。每次调用 Partition() 后数组的内容是什么，以及每次递归调用 Select() 中的参数是什么。

有人可以解释一下他们是如何解决这个问题的吗？

下面是两种算法的伪代码。

第二个代码是

我正在使用的书是Anne Kaldewaij的《算法推导》 。

我想通过一个数组并创建两个新数组：一个包含满足特定条件的元素，另一个不满足。

这是否可能一次通过，或者我必须通过两次：一次确定新数组应该有多大，然后再次填充这些数组？我可以看到这将如何与另一种编程语言或不同的数据结构一起使用，但对于 java，这似乎是不可能的。

我试图实现快速排序的就地分区子例程。它适用于唯一元素数组，但当数组包含重复元素时失败

代码是这样的

当输入是唯一元素时，代码给出正确的结果

当我尝试下面的数组时，我得到了错误的结果

这是因为我的实现有问题吗？有人可以帮忙吗？

说明：如果您有一个 n 的分区，您可以通过从分区中的最小项目中减去一个以规范的方式将其减少为 n-1 的分区。例如 1+2+3 => 2+3、2+4 => 1+4。该算法反转该过程：对于 n-1 的每个分区 p，它找到 n 的分区，该分区将通过此过程减少为 p。因此，n 的每个分区恰好输出一次，在考虑它减少到的 n-1 分区的步骤中。

这是用于在 Python 中获取数字的所有可能分区的代码。我不擅长 Python。如果有人可以将其转换为伪代码（或详细描述）或 PHP，我将不胜感激。上面的解释让我对“从分区中最小的项目中减去一个”产生了疑问。我也可以从第二小的元素或其他元素中减去一个。那么，为什么只有最小的呢？如果有人可以向我解释整个想法，那将非常感激。谢谢。

我以为我对快速排序的工作原理有很好的了解，直到我在http://code.google.com/edu/algorithms/index.html上观看了 Jon Bentley 介绍他的“漂亮的快速排序代码”的视频，如下所示：

令我困惑的算法的另一部分是 FOR 循环之后的最终交换。为什么这是必要的？让我们假设数组已经有序。如果这是真的，那么由于 x[i] > x[l] 就不会发生交换。最后，我们将 l 与 m 交换。这搞砸了订单。

我错过了什么吗？

谢谢。

我在 C# 中编写了一个并行算法，将一个数组划分为两个列表，一个包含满足给定谓词的元素，另一个列表包含不满足谓词的元素。它是一种保序算法。

我写了如下，但我想知道如何最大化从硬件并发中获利的机会。

我有一个整数的总分区，我只想要那些所有值都不相等的分区。例如，3 的分区是 {1,1,1,1}、{2,2}、{3,1}、{1,1,2} 和 {4}。因此，所需的不相等分区是 {3,1} 和 {4}，因为它们不包含相等的元素。下面提供了我用于查找所有分区的代码。我可以过滤分区以获得所需的结果，但我想要一些有效的方法来查找所有分区，其中没有相等的项，而无需找到所有分区。我已经搜索了网络和 stackoverflow，但没有确切说明我面临的问题。每一个想法都值得赞赏。谢谢。

我需要生成给定整数的所有分区。
我发现 Jerome Kelleher 的这个算法据说是最有效的：

参考：http ://homepages.ed.ac.uk/jkellehe/partitions.php

顺便说一句，它不是很有效。对于像它这样的输入40，我的整个系统几乎冻结了几秒钟，然后才给出它的输出。

如果它是一个递归算法，我会尝试用缓存函数或其他东西来装饰它以提高它的效率，但是我不知道该怎么做。

你对如何加速这个算法有什么建议吗？或者你能建议我另一个，或者另一种从头开始制作另一个的方法吗？

我需要在列表中表示一个数字的分区。该过程还接受用于确定最大分区数和初始分区最大值的参数。

这里初始总数为 5，最大分区数为 2，最大初始分区数为 4。

从概念上讲，我认为我应该将分区数字输入一个辅助函数，该函数将为我构建分区。但是我将如何实现呢？

解决了