问题标签 [powerset]

我在网上找到了许多具有 O(2^n) 复杂性的解决方案。有人可以帮我弄清楚下面给出的代码的时间复杂度。它还涉及很多位操作，我在这方面真的很弱，所以我不太了解代码的窍门。如果有人可以解释代码，那就太好了。

这是最优化的解决方案吗？

我正在尝试编写一个 java 方法来查找字符串的子集，但我不断收到我无法调试的运行时错误。这是代码：

嗨，我已经看过论坛了，但没有找到解决我问题的方法。问题是：我怎样才能找到 S 大小的列表的所有可能子集[长度为 l]。并将其返回到列表中。

给定一个可索引的数据结构，比如 vector = ['a','b','c'] 大小为 n=3 和 int i = 3，我想将 3 转换为它的 n 位二进制表示（011 ) 并返回向量的元素 ['b','c']。也就是说，对于二进制表示中的每个 1，返回该位置的元素。但是我如何谈论二进制数中的“位置”？我无法将一个想法映射到另一个想法。任何帮助表示赞赏。

更新：@bphelpsjr 答案提供了我正在寻找的内容。不幸的是，有人对他投了反对票，而我没有代表支持。我将他的回答标记为答案。

这是非常冗长的，但我想提供尽可能多的细节。

本质上，我想获取一组数据并根据规则（定义如下）生成列表列表。这本质上是 powerset 的过滤版本。

然后我将存储这些结果以供重复使用（类似于彩虹表）以避免不断计算相同的结果N。然后我将在应用其他逻辑之前使用变量替换（例如，A = 18，B = 30）（下面没有描述，我的问题不是必需的）。

这是我在尝试创建解决方案时尝试过的两个输入选项。您也可以使用数字代替字母。

输入选项#1

输入选项 #2

期望的输出

规则

前 3 条是明确的规则，而第 4 条则更多是一种愿望。

1. 解决方案必须能够处理N个不同的字母和项目列表

2. 每个不同的字母必须在项目列表中至少出现一次。例子：

   AA BB CC DD <-- 有效

   AA BB CC <-- 无效，不包含 D

3. 字母只能在给定项目内重复。例子：

   AA BB CC DD <-- 有效

   AA BA CC DD <-- 无效，A 在不同项目中重复

4. 逻辑必须包含尽可能多的“积极过滤”和短路，以减少它将执行的迭代次数。我有一个可行的左移解决方案，但由于（我的？）无法合并过滤和短路，它无法扩展。这基本上导致了对整个 powerset 的迭代。

   • 示例：一旦找到已包含在潜在列表项中的字母，请继续下一个可能的组合，因为该组合无效。

   • 示例：一旦找到有效的项目列表，就开始下一轮。

接下来的两个是基于我目前将数据集按每个项目的第一个字母分组的方式的潜在示例。根据您创建的解决方案类型，它们可能不适用。

• 潜在示例：如果某个项目包含位于下一个列表项目中的字母，则跳过整个列表并移至下一个项目列表。

  AA BC DD <-- 我们可以跳过 C 列表，因为它被 BC 覆盖

• 潜在示例：一旦您用尽了列表的潜在候选人（例如，最后一个列表将只有 1 个项目），您不应该（如果我的想法是正确的）再次需要该列表，直到它上面的列表 + 1 更改了项目.

  AA BB CC DD <-- 找到这个之后，停止搜索包含 DD 的列表，直到到达 BC（DD + 1 上方的列表）

  AA BB光盘

  AA BC DD <-- 我们又需要 DD

  1. 无论项目的顺序如何，任何项目列表都不应重复。例子：

  AA BB CC DD == BB AA DD CC 所以不包括 BB AA DD CC

我所做的假设：

• 通过它们的初始起始字母对集合进行分组会更容易（参见下面的示例数据）。如果这不是最佳方法，那也不是问题。

下面是我用来保存数据的 Item 类，只是为了方便：

我正在尝试生成图中节点元素列表的幂集。我已经从上一篇文章中识别并修改了以下代码（集合的唯一组合）

我正在使用测试功能

但是，我得到一个指向 PowerSet 函数中的函数（a，b）的无效转换异常错误：

附加信息：无法转换类型为“WhereSelectListIterator 2[System.Collections.Generic.List1[cDAG_with_classes.Node],System.Collections.Generic.IEnumerable 1[cDAG_with_classes.Node]]' to type 'System.Collections.Generic.IEnumerable1[System.Collections.Generic.List`1[cDAG_with_classes.Node]]”的对象。

任何人都可以就我可能出错的地方提供一些建议吗？

谢谢

我需要一个简单的 java 程序，它可以为我生成一组自定义集，比如 {'1','2','3','4'}。结果应该是：{'1','2'},{'2','3'},{'3','4'},{'1','2','3'},{ '2'，'3'，'4'}。

我已经尝试过 powerset 的代码，但输出并不理想。如果代码可能类似于：

我知道 .size() 用于 ArrayList 而 a[i] 用于简单数组，我已经编写了任何方法都可以！提前致谢！！:)

我想编写用于邻接矩阵的最大团算法。我正在观看一段视频，该视频解释了如何使用 Python 编写和实现算法。我目前正在尝试在视频 2 分钟后对 powerset 功能进行编码。

我想用 C++ 重写它。我不确定我是否应该使用数组。到目前为止，我已经编写了以下代码，但我不知道如何在空数组中返回一个空数组（当elts list大小为 0 时）。

我为数组编写了一个isEmpty函数，因为我不能len(elts)像在 Python 中那样使用。我的方法可能不是最好的方法，所以我愿意接受任何建议。

更新：

在我的 int main 我有：

我不知道从这里做什么。

代码应该使用我们称之为“elts”（元素的缩写）的array// 。然后首先，它应该添加空列表，然后是电源集的其余部分（全部显示在视频中）。listvector[]

例如，在这种情况下elts = [1,2,3,4]，我的代码应该返回：

我不知道如何使用array//来做上面的事情list。vector

考虑以下字符串

我可以像这样返回 2 个字符排列（笛卡尔积）

但是我想删除多余的条目，例如

和无效条目

所以我只剩下

例子

我正在准备面试，我在网上的“数学”类别下偶然发现了这个问题。

生成给定集合的幂集：

请我不要一个明确的答案。我只是想要关于如何解决这个问题的澄清和提示。

我在谷歌上检查了功率集算法，但我仍然不明白如何解决这个问题。

另外，有人可以重申这个问题的要求。

谢谢你。