问题标签 [powerset]

我想生成一个 set 的P(S)powerset S。我只想P(S)拥有等于某个大小的子集。

例如，如果我们有S = [1,2,3,4]，那么limited_powerset(S,3)将是[[1,2,3],[2,3,4],[1,3,4],[1,2,4]].

Hynek Pichi Vychodil提供了一个在 Erlang 中生成通用 powerset 的好例子（谢谢！）：

如何修改它以仅具有特定大小的子集？引入一个 Limit 变量并将最后一行更改为

没有帮助。

PS我猜子集的数量会小于N！但我怎么能准确地计算出来呢？

我想计算一组的幂集。因为我一次不需要整个powerset，所以最好懒惰地生成它。

例如：

由于结果是一个序列，所以我更喜欢上面的顺序。如何在 F# 中以惯用的方式做到这一点？

编辑：

这就是我要使用的（基于 BLUEPIXY 的回答）：

感谢大家的出色投入。

我想生成一个相当大的集合（大约 30-50 个元素）2^n的 powerset，我知道存储 powerset 需要。

是否可以一次生成一个子集？

即通过迭代生成一个集合的powerset，将每个生成的子集保存到磁盘/数据库，将其从堆栈/内存中删除，然后才继续生成其他子集？

不幸的是，我未能根据我的需要修改Erlang和Ruby示例。

注意：这是我之前关于 powerset 的问题的续集。

我有一个很好的 Ruby 解决方案来解决我之前关于在不需要保留堆栈的情况下生成集合的 powerset 的问题：

它可以完成工作并且效果很好。

但是，我想尝试在 Erlang 中重写相同的解决方案，因为对于该{|item| p item}块，我已经用 Erlang 编写了大部分工作代码（它对每个生成的子集都做了一些事情）。

虽然我对 Erlang 有一些经验（我已经阅读了所有 2 本书 :)），但我对sepp2k对我之前关于 powersets 的问题的示例和评论感到非常困惑。我不明白示例的最后一行 - 我唯一知道的是列表理解。我不明白如何修改它以便能够对每个生成的子集执行某些操作（然后将其丢弃并继续下一个子集）。

如何在 Erlang 中重写这个 Ruby 迭代 powerset 生成？或者也许提供的 Erlang 示例已经几乎满足了需要？

我知道“幂集只是 0 到 2^N-1 之间的任意数字，其中 N 是集合成员的数量，二进制表示中的一个表示存在相应的成员”。

( Hynek-Pichi-Vychodil )

我想使用从二进制表示到实际集合元素的这种映射来生成一个幂集。

我怎么能用 Erlang 做到这一点？

我试图修改这个，但没有成功。

UPD：我的目标是编写一个迭代算法，在不保留堆栈的情况下生成一个集合的幂集。我倾向于认为二进制表示可以帮助我解决这个问题。

这是 Ruby 中成功的解决方案，但我需要用 Erlang 编写。

UPD2： 这是伪代码的解决方案，我想在 Erlang 中做类似的事情。

假设我们有一个S包含几个子集的 Set：

假设 S 包含六个独特的元素：a, b, c, d, e和f。

我们如何才能找到所有可能的子集，S其中包含S恰好一次的每个独特元素？

函数/方法的结果应该是这样的：

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

是否有任何最佳实践或任何标准方法来实现这一目标？

如果提供伪代码、Ruby 或 Erlang 示例，我将不胜感激。

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

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

以及以下“独特”元素：

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

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

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

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

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

例如，如果我有序列 [1,2,3]，那么生成子序列的算法是什么：

但不是

也不

然后我希望将这些作为键插入字典中，以及在形成值的数据库中查找这些唯一子集的结果。我想知道你是否可以帮忙？

非常感谢！

我必须写一个背包问题的蛮力实现。这是伪代码：

虽然该算法相当容易实现，但我一点也不知道如何生成 S 的幂集，以及如何将幂集的子集输入到 while 循环的每次迭代中。

我当前的实现使用一对列表来保存项目的重量和利润：

我想为我的 computeMaxProfit 函数生成这个列表的幂集。是否有一种算法可以生成列表的子集？列表是正确的容器吗？

我有一组数字：

我需要从它们那里获取组合，其中每个新对只能在后一个数字与该对中的第一个数字相同的情况下附加。

例如，如果我有一对 {15,1}，下一个只能是 {1,46} 和下一个 {46,45}，最后一对必须以整个集合的第一个数字结尾。在这种情况下，它可能是例如 {45,1}。

因此，具有 4 个集合限制的集合的最终结果将是

我可以做基本的幂集并从一组数字中生成所有可能的组合，但这对我来说似乎太先进了。

我可以使用 C、Javascript 或 PHP，因此非常感谢所有帮助或解决方案。澄清一下，这不是作业，这只是我想学习和理解的东西。