问题标签 [powerset]

我理解并在 F# 中编写了一个典型的幂集函数（类似于Wikipedia中的算法部分）

后来我发现这个 powerset 的实现看起来不错而且很紧凑，希望我不明白。

我将其分解为 1 步非递归函数，以找到 [1;2] 的幂集，并在末尾硬编码 2 的幂集值 [[2]; []]

输出[[1]; []; [1; 2]; [2]]是正确的。

但是我期待 List.Fold 输出[[1; 2]; []; [1; 2]; [2]]。

由于我不确定't'，我修改了变量名，我确实得到了我所期望的。当然，这不是 [1;2] 的正确幂集。

对我来说，'t'（有趣而不是 h::t）只是 'fun' 的第二个参数的名称，但显然情况并非如此。那么我写的“正确”和“错误”F#函数有什么区别呢？这里的“不”到底指的是什么？

谢谢 ！（我是 F# 的新手）

我在看Data.Set，发现它没有任何powerset功能。为什么？

我可以像这样实现它：

但这似乎不是最有效的方法。好的，我也可以写

但是，我仍然想知道为什么Data.Set没有powerset功能。

另外，最好的写作方式是powerset :: (Ord a) => Set a -> Set (Set a)什么？

我正在尝试查找向量/项目列表的所有唯一分组，长度为 39。以下是我拥有的代码：

但是，该代码导致我的计算机内存不足。有一个更好的方法吗？我意识到我有一个很大的清单。谢谢。

我有一个元素列表（1、2、3），我需要获取该列表的超集（幂集）（不重复元素）。所以基本上我需要创建一个列表列表，如下所示：

实现这一点的最佳方式是什么（在这种情况下简单> 效率，列表不会很大）？最好使用 Java，但任何语言的解决方案都会很有用。

给定 PHP 中的元素数组，我希望创建一个新的二维数组，其中仅包含特定长度的幂集元素。例如，对于以下数组：

如果我要运行该函数，fixed_length_power_set( $arr, 2 )那么我希望它返回：

虽然我可以想出一些规则来概括这个过程，但由于某种原因，我似乎无法将其转化为代码。有人有建议吗？

尝试计算 9 个字母字符串 'ABCDEFGHI' 的所有子集（幂集）。

使用标准递归方法，我的机器在完成之前遇到内存不足 (1GB) 错误。我没有更多的物理记忆。

怎样才能做得更好？语言没有问题，发送到标准输出的结果也很好——输出前不需要全部保存在内存中。

在 Java、Python 和其他语言中有很多生成集合的幂集的示例实现，但我仍然无法理解实际算法是如何工作的。

算法采取哪些步骤来生成集合 S 的幂集 P(S)？

（例如 {1,2,3,4} 的幂集是 {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3 }，{1,2,3}，{4}，{1,4}，{2,4}，{1,2,4}，{3,4}，{1,3,4}，{2 ,3,4}, {1,2,3,4}}。）

UPD：我找到了这个解释，但我还是不明白。我试图理解生成幂集的算法，因为我想编写它的并行实现——下面的顺序 Erlang 实现有一个巨大的堆栈，在一台 8 GB 的机器上不能计算超过 30 个元素集内存：

UPD2：

此代码段返回集合 [a,b,c] 的所有子集，除了 [a,b,c]：

我不确定这个片段是否正确。

我有两个顶点列表：V和S.

我想从等生成所有可能的有向图V，S每个顶点V只有一个出边和一个入边，每个顶点S可以有任意数量的入边和出边。结果中的每个图都应包含来自V和 的所有顶点S。结果可以包含连通图和不连通图。

首先我认为这是一个与 powerset 相关的问题，但是 powerset 有许多其他的集合可能只包含一个元素（我不需要那些）。

我目前的策略是：

• 找到顶点之间的所有对V，添加到Pairs；
• 找到顶点之间的所有对S，添加到Pairs；
• V从和中找到所有顶点之间的对S，添加到Pairs;
• 生成大小不小于V这样的对子集，每个子​​集在第一个位置恰好有一个顶点v实例，在第二个位置有一个顶点实例，以及来自任何位置v的任意数量的任何顶点实例.sS

我不确定这是否正确，我想知道任何想法。

也许我可以从中创建一个完全连接的图G，V然后S以某种方式从中提取子图？（也许在 digraph:utils 的帮助下）

PS 我正在尝试在 Erlang 中解决这个问题，因为它是我现在正在使用并积极学习的语言。但我很高兴在答案中看到 Java、Ruby 或伪代码。

假设我们有一个集合 S = [a,b,c,d,e,f]。我们有一个集合 N = [1,2,3]。

我们如何在所有可能的组合中将 S 的元素分配给 N 的元素？

期望的结果将是这样的：

1. [1,[a]], [2,[b,c]], [3,[d,e,f]]。
2. [1,[a]], [2,[b,c,d]],[3,[e,f]]。
3. 等等

是powerset生成问题还是其他问题？如何找到它的复杂度和空间复杂度？

如何生成这些子集？

假设我们有一个完全连通的有向图G。顶点是[a,b,c]。每个顶点之间都有两个方向的边。

给定一个起始 vertex a，我想在所有方向上遍历图形并仅在遇到路径中已经存在的顶点时才保存路径。

所以，函数full_paths(a,G)应该返回：

我不需要像[{a,b}]or这样的“不完整”结果[{a,b}, {b,c}]，因为它已经包含在第一个结果中。

除了生成 G 的幂集并过滤掉一定大小的结果之外，还有其他方法吗？

我该如何计算？

编辑：正如 Ethan 指出的，这可以通过深度优先搜索方法来解决，但不幸的是我不明白如何修改它，使其在回溯之前存储路径（我使用 Ruby Gratr来实现我的算法）