问题标签 [powerset]

我正在使用以下 C# 函数来获取限制为最小长度子集的 powerset

问题是当原始集合很大时，即使最小长度也很大，算法也必须非常努力。

例如：

应该很容易，但对于上述功能来说太冗长了。我正在寻找可以有效处理这些情况的函数的简洁修改。

我希望定义一个谓词 powerset(X, P)，当 P 是 X 的幂集时它为真。无论 P 是否接地，都应该有效。

是否可以在计算字符串的幂集（即该字符串的所有可能子序列）时使用动态规划来显着减少计算次数？

在 n=5 和 k=3 的情况下，以下循环将执行此操作

但效率不高我想用银行家的序列来做，因此先探索单例，然后是对，然后是三元组并停止。

我没有找到这样做的方法，但至少这个循环应该更有效：

还有：但是k个嵌入式循环看起来很难看

我有一个列表，我想将其拆分为包含 +/- 1 个项目的子列表。

例子

我有一个包含 17 个项目的列表。我想要的是把它分成4个像这样的子列表

我怎样才能做到这一点？我应该在这里使用什么算法？

假设我有以下课程：

以及可能具有的上述类对象的列表：

我只想做以下事情：

任何人都可以建议我如何在Java中做到这一点（如果可能的话，使用一些示例代码）。

谢谢！

我正在尝试编写一种方法来计算顺序很重要的幂集的所有排列。我相信这些被称为“安排”。我的意思是：

等等。我的印象是，给定一个集合 S，我应该生成 S 的幂集的每个子集的每个排列。所以首先生成幂集，然后将一个置换函数映射到每个集合上。

问题是这非常复杂——类似于 O(∑n!/k!) ，k=0..n。

我想知道是否有任何现有的算法可以非常有效地完成这类事情（也许是并行实现）。或者即使存在并行幂集算法并且存在并行置换算法，我也可以将两者结合起来。

想法？

我遇到了一个从 arrayList 制作子集或 powersets 的问题，其中可能是 70 或 80 个或更多 String 元素，然后进一步处理这些子集（或 powersets）。例如，我有一些 arrayLists 具有不重复的字符串作为元素，如下所示（字符串实际上有多个字符）：

然后我需要让子集（或 powersets）包含第一个元素。例如：{a,g}, {a,b}, {a,n,f}, {a,g,n,f}....

我已经完成了这项工作，方法是获取除第一个之外的列表元素的 powerset，然后将第一个元素与这些子集相加。但这适用于像 7 或 8 这样的少数元素，但如果列表增长则无法工作。是否需要像我为这份工作做的那样做一个 powerSet 算法？如果没有，那么我怎样才能得到预期的结果。我认为存在内存泄漏问题。因为我需要存储这些结果以进行进一步处理。

我按照以下链接的一些建议完成了这项工作：

在Java中获取一个集合
的幂集计算一组数字的所有子集
如何从arrayList对象生成所有可能的幂集（或子集）？

但是对于大型列表来说，这些需要花费很多时间并且最终无法获得结果，因为我的 netbeans IDE 被绞死了！

我需要一些与此方案相关的建议或示例代码。

谢谢！

I have a Set of items of some type and want to generate its power set.

I searched the web and couldn't find any Scala code that adresses this specific task.

This is what I came up with. It allows you to restrict the cardinality of the sets produced by the length parameter.

This will not include the empty set. To accomplish this you would have to change the last line of the method simply to res + Set()

Any suggestions how this can be accomplished in a more functional style?

如何明确地写出一个幂集与另一个集的笛卡尔积。

例如：P({a,b})x{a,b}

现在 P({a,b}) = {{},{a},{b},{a,b}}

所以我需要知道 {{},{a},{b},{a,b}}x{a,b}