algorithm - 哪种算法可以计算给定集合的幂集？

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

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

result =

[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]

注意。我不需要重复的组合，尽管我可以使用它们，例如，在上面的示例中，我实际上并不需要组合[1,3,2]，因为它已经显示为[1,2,3]

最佳答案

您要问的名字有一个。它称为power set。

搜寻“功率集算法”使我想到了这个recursive solution。

Ruby算法

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)
   subset | subset.map { |x| x | [p] }
end

功率设定直觉

如果S =(a，b，c)，则幂集(S)是所有子集的集合
powerset(S)= {()，(a)，(b)，(c)，(a，b)，(a，c)，(b，c)，(a，b，c)}

第一个“技巧”是尝试递归地定义。

什么是停止状态？

S =()具有什么幂集(S)？

如何获得？

减少一组元素

考虑取出一个元素-在上面的示例中，取出{c}

S =(a，b)，然后幂集(S)= {()，(a)，(b)，(a，b)}

什么东西少了？

powerset(S)= {(c)，(a，c)，(b，c)，(a，b，c)}

嗯

有任何相似之处吗？再看...

powerset(S)= {()，(a)，(b)，(c)，(a，b)，(a，c)，(b，c)，(a，b，c)}

取出任何元素

powerset(S)= {()，(a)，(b)，(c)，(a，b)，(a，c)，(b，c)，(a，b，c)} 是

powerset(S-{c})= {()，(a)，(b)，(a，b)}与

{c} U powerset(S-{c})= {(c)，(a，c)，(b，c)，(a，b，c)}

powerset(S)= powerset(S-{ei})U({ei} U powerset(S-{ei}))

其中ei是S的元素(单例)

伪算法

传递的集是否为空？完成(请注意，{}的幂集为{{}})

如果没有，取出一个元素

在集合

的其余部分上递归调用方法

返回由联合组成的集合

不包含元素的集合的幂集(来自递归调用)

这是相同的集合(即2.1)，但其中的每个元素都与最初取出的元素结合在一起

关于algorithm - 哪种算法可以计算给定集合的幂集？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2779094/