问题标签 [powerset]

给定输入数组

和一个“加入”功能(a,b) => (a+b)

我的代码返回以下数组数组，其中包含通过将连接函数应用于各种元素对同时保持顺序而获得的每个可能的变化：

在视觉上，我想要做的是：

该代码有效，但我不知道该怎么称呼它 - 如果存在这样的名称，我想使用其他熟悉此操作的开发人员会理解的名称。它不是一个幂集，但它是类似的……这个特定的集合/数组操作有名字吗？

编辑：好的。它们不是排列；排列都将是不同顺序的 5 元素数组[[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

它们不是partitions，因为任何子集只能包含输入的相邻元素。- 换句话说，分区将允许这样做：

（这可能源于没有有序集合概念的纯集合论。）

它们不是组合，因为输出的每个元素只使用输入集的每个成员一次。

我认为myArray.OrderedPartitions((a,b) => (a+b))可能是一个适当简洁和解释性的。

为了获得列表的幂集，我实现了以下内容：

这是使用递归获取列表幂集的最佳方法吗？我已经看到了很多关于如何在互联网上实现这一点的不同方法，但它们似乎比我的复制（使用新的）更多。

例如，这个StackOverlow 帖子出现在我的 Google 搜索中，但他的实现 (Joao Silva) 使用了大量的复制，并且似乎不是最佳的。但是，我经常看到他的实现，这让我很困惑。该实现是否比我正在使用的更好（当然，他正在使用泛型这一事实）？

他的代码：

Let S(w) be a set of words. I want to generate all the possible n-combination of subsets s so that the union of those subsets are always equal to S(w).

So you have a set (a, b, c, d, e) and you wan't all the 3-combinations:

((a, b, c), (d), (e))

((a, b), (c, d), (e))

((a), (b, c, d), (e))

((a), (b, c), (d, e))

etc ...

For each combination you have 3 set and the union of those set is the original set. No empty set, no missing element.

There must be a way to do that using itertools.combination + collection.Counter but I can't even start somewhere... Can someone help ?

Luke

EDIT: I would need to capture all the possible combination, including:

((a, e), (b, d) (c))

etc ...

我在任何地方都找不到答案，所以这是我的解决方案。

问题是：如何计算 R 中的幂集？

可以使用库“sets”执行此操作，使用命令2^as.set(c(1,2,3,4))产生输出{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}。但是，这使用了递归算法，速度相当慢。

这是我想出的算法。

它是非递归的，因此它比其他一些解决方案快得多（在我的机器上比“sets”包中的算法快约 100 倍）。速度仍然是 O(2^n)。

该算法的概念基础如下：

这是R代码：

编辑：这是同一概念的更快版本；我的原始算法在这篇文章的第三条评论中。对于一组长度为 19 的机器，这个在我的机器上快 30%。

此版本通过在开始时使用其最终长度初始化向量并跟踪保存新子集的位置的“计数器”变量来节省时间。也可以通过分析计算位置，但速度稍慢。

我正在尝试使用生成器在 Python 中构建给定集合的子集列表。说我有

set([1, 2, 3])

作为输入，我应该有

[set([1, 2, 3]), set([2, 3]), set([1, 3]), set([3]), set([1, 2]), set([2]), set([1]), set([])]

作为输出。我怎样才能做到这一点？

我有这个代码，它生成一个大小为 4 的数组的幂集（数字只是示例，要编写的组合更少......）。

输出：

我需要那个输出是这样的：

所以必须这样订购。我不能在算法结束后进行排序，我必须在每次迭代中使用每个组合，所以它必须生成已经排序的组合。有人可以帮我吗？我想我什么都想好了……

编辑：最终输出应该没有空集，但这不是优先级。

我想先说这是一个学校作业，所以当我需要帮助时，最好为我指出正确的方向，而不是给我代码来使用。

因此，任务是能够打印出任何给定集合的 PowerSet（给定集合的所有子集的集合）。我对 Java 有一定的经验，但递归是我的弱点之一，所以我很难想象这一点。

我的方法返回所有包含“d”和空集的子集。

这是我到目前为止所拥有的：

给定集合

这个方法给了我一套

但我们知道 PowerSet 应该是

任何朝着正确方向发展的帮助将不胜感激。

编辑：我的问题是一个非常愚蠢的问题。我忘记正确设置比较器，它排除了结果。我修复了比较器以正确排序而不会丢弃集合。

这里是：

I have code below that does exactly what I want the program to do. The only problem is I don't even know where to get started to make the methods recursive. I understand using recursion for factorials and other problems but this one is over my head a bit. Can anyone help point me in the right direction?

我正在尝试递归地找到一个集合的幂集，然后打印我非常坚持的结果，任何帮助将不胜感激。

我正在使用带有 DrRacket 列表缩写的起始语言，并且想要递归地创建一个 powerset，但无法弄清楚如何去做。我目前有这么多

任何帮助都会很好。