问题标签 [powerset]

给定一组{1,2,3,4,5...n}n 个元素，我们需要找到长度为 k 的所有子集。

例如，如果 n = 4 且 k = 2，output则{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

我什至不知道如何开始。我们不必使用诸如 next_permutation 等内置库函数。

需要 C/C++ 或 Java 中的算法和实现。

我正在尝试编写 python 代码来打印字符串的powerset，但遇到了一些错误。这是我所拥有的：

我的预期输出是：

我的实际输出是：

谁能帮我弄清楚发生了什么？这是python的一些细微差别，还是我的代码中有错误？我认为我的代码应该没问题——我要离开第五版破解编码面试

谢谢！

我们在 MySQL 中有一个产品表，其中每一行都有一个以逗号分隔的选项值的字段，这些选项组合成这个产品。在下面的方案中，您可以看到两个表。逗号分隔值的字段是 option_ids，例如，这可能看起来像 2、5、6、23 或 4、2、76。这些数字是选项表中存在的选项。

产品：
|product_id|name|description|option_ids|price|

选项：
|option_id|type_id|label|group|pos|count|price|

我们得到的输入是一组独特的选项。我们想在 option_ids 中找到具有这组选项或其子集的每个产品。

我们现在这样做的方法是生成选项数组的幂集，以便我们拥有选项数组的所有可能组合。然后我们生成一个 mysql 查询，用于查询“OR WHERE”语句中的所有这些组合。

这里的问题是幂集呈指数增长，所以当我们有一个包含 16 个唯一选项的数组时，幂集给出了一个包含 65536 种可能性的数组。我们必须增加 php 的内存使用量才能正常工作，但现在我们遇到了 MySQL 问题，因为查询变得如此庞大。

有没有另一种方法来解决这个问题？

我希望我已经提供了足够的信息，如果没有，请询​​问！

编辑：第三张表会给我们带来同样的问题，因为我们需要找到子集......这并不是说一系列选项是一个产品，它可以是一个产品，但也可以是 2 或 3 个产品。例如：选项 1,2 制作产品 A，选项 2,3 制作产品 B，选项 4,5,6 制作产品 C。如果我们有选项数组 [1,2,4,5,6]，我们希望找到产品 A 和 C。

我试图将 powerset 写入文件，但如果我的起始数组大于大小 6，我会得到堆损坏，我不知道为什么。它适用于任何大小的数组 6 或以下。想不通这个。

此外， test.txt 是我在数组中读取的位置。如果文件包含“1,2,3,4,5,6”它工作正常，但它包含“1,2,3,4,5,6,7”我得到堆损坏。

我在这里遇到一个问题，我需要生成所有可能的对象组合并将它们存储在列表中以供稍后分析..

Internet 上的搜索包括许多算法，这些算法无法满足存储组合的要求。大多数常见的搜索只是通过打印出来来生成组合列表，而其他搜索只处理字符串，而不是对象。

一些算法使用位来表示不同的组合，但这种解决方案最多只能限制 32 个对象，这还不够好。

总的来说，我正在寻找一种算法，我可以在其中生成所有可能的组合（幂集），处理对象（超过 32 个），并且不仅限于打印出组合，而是将这些组合存储在数组。

我正在尝试n-th在 powerset 中找到该集合。我的意思是，powerset 是按n-th以下顺序生成的——首先是大小，然后是字典顺序——因此，powerset 中的集合的索引[a, b, c]是：

在寻找解决方案时，我能找到的只是一个返回元素列表的第 n 个排列的算法——例如，这里.

上下文：

我正在尝试检索V元素向量的整个幂集，但我需要一次只使用一组。

要求：

• 我只能同时维护两个向量，第一个包含列表中的原始项目，第二个包含n-th来自 powerset 的集合V——这就是我愿意在n-th set这里有一个函数的原因；
• 我需要不要在解决方案空间上以线性时间完成此操作——这意味着它不能列出所有集合并且他们选择n-th一个；
• 我最初的想法是使用位来表示位置，并获得我需要的有效映射 - 作为我发布的“不完整”解决方案。

我正在为我的 Java 编程作业寻求一些帮助。使用链表，我需要打印出它的幂集。例如，集合 {1,2,3} 应打印出 {{},{1}{1,2}{1,3}{1,2,3}{2}{2,3}{3} }。幂集中的元素个数为 2^n。这需要通过调用 HeadNode.PrintPowerSet(); 来完成。
其中 HeadNode 是链表中的第一个元素。我已经尝试了一些东西，但没有什么效果那么好。我认为最好的方法是递归调用该方法，直到到达终点哨兵，然后向后工作，添加剩下的元素。抱歉，我无法发布更多代码或更多想法，因为我尝试过的任何东西都没有那么好。提前致谢。

编辑：这是非工作代码。它返回集合 {{1,2,3}{2,3}{3}}

EMPTY_SET 是结束标记。我试过用手把它写出来。它有帮助，但我仍然无法得到它。同样，RSet 这个类本质上只是一个链表节点。

我正在尝试生成一组的幂集，并且我编写了这段代码。问题是，当用户输入两个相似的集合成员时，它不能正常工作。我能做些什么？这是我的代码：

一切都在标题中.. =）

我想快速创建一个powerset，只有长度子集在3（最小恒定长度）和最大值之间。这个最大值在大多数情况下应该是 5，但我希望它是可变的（从 3 到 5,6）。原始集可能很大。我需要存储这些子集以供进一步处理。

我已经看到了在 Java 中获取一个集合的幂集，但是在这里它们生成了幂集的每个子集。对于 C#，我还看到了用于最小长度子集的有效 powerset 算法，但我认为，正如 Adam S 所说，我会遇到低运行时间性能和内存问题。

我想将这些想法组合成一个理想的实现我的目标。我最后的希望是快速生成每个子集（也许使用Guava中的算法）并迭代以仅采用所需的长度......但即使阅读它也很丑;）

有人有想法吗？

我编写的一个小应用程序允许用户将各种项目添加到两个数组中。一些逻辑根据每个数组的内容计算一个数字。

数组 x 中的任何项目都可以放入数组 y 中，然后再放回去。属于数组 y 的项永远不能移动（除非它们是从数组 x 中移动的）。

用户可以使用简单的 javascript ui 在两个列表中移动这些项目。为了让事情更简单，我最初制作了一个简单的脚本：

1. 将项目从 a 移动到 y。
2. 使用这种“可能性”执行了一些逻辑
3. 如果结果小于以前，则将 x 留在 y 中。
4. 如果不是，则 x 保留在 x 中。
5. 移动到 x 中的下一项并重复。

我知道这是无效的。我已经阅读并被告知使用按位数学来记住可能性或“排列”，但在这个阶段我正在努力解决这个特定问题。

如果有人能够解释（伪代码很好）什么是实现以下目标的最佳方法，我将不胜感激。

数组 x = [100,200,300,400,500] 数组 y = [50,150,350,900]

使用这两个数组，对于来自 x 的每个值，将该值和来自 x 的所有其他值的每个组合推入数组 y。对于每一个，我将执行一些逻辑（即测试结果并将这个“排列”存储在一个数组中（一个代表 x 和 y 的两个数组的对象）。我预见这对于大型数组来说非常昂贵，可能会重复很多我觉得我快到了，但在最后阶段迷路了。

抱歉，解释太长了，在此先感谢！