问题标签 [powerset]

给定一个集合

我怎样才能产生子集：

的幂集{1, 2, 3}是：

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

假设我Set在 Java 中有一个：

如何以尽可能好的复杂性顺序编写函数 getPowerset？（我认为它可能是 O(2^n)。）

这可能与语言无关/有用的答案可能只是伪代码。

我有一个程序，我想在一系列输入下进行测试。该程序采用一组文件，其中一个被指定为根。我想用所有可能的文件子集运行程序。（包含相同文件但具有不同根的两个子集被认为是不同的。）

这是一个相同的例子。假设我有文件 A、B 和 C。我想测试：

等等。我相信这将是动力装置。

给定一个充满文件的目录，在 Java 中生成这个集合的最佳方法是什么？

是否有一些等效的库或函数可以为我提供一组值的下一个组合，例如 next_permutation in 对我有用吗？

我想根据数字的起始列表有效地生成唯一的数字组合列表。

示例开始list = [1,2,3,4,5]，但算法应该适用于[1,2,3...n]

笔记。我不想要重复的组合，尽管我可以忍受它们，例如在上面的例子中我并不真正需要组合 [1,3,2] 因为它已经显示为 [1,2,3]

可能的重复：
显示字符串
算法的可能组合，该算法将采用数字或单词并找到所有可能的组合

如果我有 3 个字符串，例如：

我想通过重新排列这些字符串来找到我可以生成的最大组合数，例如：

• abc xyz 定义
• 定义 xyz abc
• xyz abc def

等等。计算这个的公式/算法是什么？

对于我现在正在处理的问题，我希望从给定集合的幂集中进行合理统一的随机选择。不幸的是，这正好涉及统计数据，这是我根本没有研究过的东西（现在我正在进入真正的编程领域，我需要纠正一些东西）所以我想在一些知道它的人面前运行我的解决方案。

如果给定集合的大小为 n，则有 (nk) = n!/[k!(nk)!] 个大小为 k 的子集，并且幂集的总大小 N 为 (nk) 与 k 的总和0 到 n。（也以 2 ⁿ给出，但我认为这在这里没有用。我可能显然是错的）。

所以我的计划是将 [0, 1] 划分为区间：

在算法上，区间是通过将前一个区间的最大元素作为新区间的最大下限加上 (nj)/N 以获得最大元素来构造的。我希望这很清楚。

然后我可以通过在 [0, 1] 中选择一个统一的浮点数并将其映射到它所属的区间的索引来确定随机子集中有多少元素。从那里，我可以选择适当大小的随机子集。

1. 我很确定（仅从直观的角度来看）我的方案在子集的大小上提供了统一的选择（相对于子集的总量是统一的。在集合 {1, 2, .., n} 个尺寸）。

2. 我正在使用一个库（python's random.sample）来获取给定大小的子集，所以我相信这将是统一的。

所以我的问题是，如果按照我所描述的方式将两者放在一起，是否会使随机大小的随机子集的选择变得统一。如果答案是大量工作，那么我很乐意接受有关如何证明这一点并为自己完成工作的指示。另外，如果有更好的方法来做到这一点，那么我当然会对此感到高兴。

给出以下集合：

我定义了集合：

你为工会

幂集运算的结果集是：

0表示空集

我的问题涉及到 unio 操作。我如何联合 0 和 Y？

实际上，我有一组具有概率的对象，我想查看它们中的每个可能组，按照假设它们是独立的，它们都是真实的可能性有多大 - 即按降序排列子集元素的乘积 - 如果概率相同，则按长度顺序排列（因此 (1, 0.5) 在 (0.5) 之后）。

示例：如果我有[ 1, 0.5, 0.1 ]我想要[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

从本质上讲，这意味着我想按顺序迭代一组元素的幂集，并且我可以相当容易地生成它，对其进行排序并完成。然而，powersets 变得相当大很快，我希望我通常会想要第一个子集，我宁愿不生成数千个子集的列表，对它们进行排序，然后再看第三个。这就是 python 生成器希望拯救这一天的地方！

更正式的问题说明，我需要找到一种方法sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)，作为生成器，或者以其他方式让我避免构建和排序整个列表。

我有理由确定这与背包问题以及子产品问题有关，但我真的很难找到一个很好的算法来解决它，非常感谢您的帮助:-)。在最坏的情况下（一直迭代到最后），它比构建+排序整个事情要慢并不是问题，它只需要更好的最佳情况（比如说，在前 10% 内）性能。

我有一个算法可以使用 0 到 2^n 之间的所有位来计算集合的幂集：

我的问题是：这个算法的运行时间是多少。该循环运行 2^n 次，并且在每次迭代中，while 循环运行 lg(i) 次。所以我认为运行时间是

T(n) = the sum from i=0 to i=2^n of lg(i)

但我不知道如何进一步简化，我知道这可以在 O(2^n) 时间（而不是空间）递归地解决，所以我想知道上面的方法是否比这更好或更差，时间上为在太空中更好。