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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

示例开始，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]

回答：

您要问的名字有一个。这就是功率集。

谷歌搜索“功率集算法”使我想到了这种递归解决方案。

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）是一组的所有子集的 幂集 （S）= {（）中，（a），（B），（C），（A，B），（

a，c），（b，c），（a，b，c）}

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

什么是停止状态？

S =（）具有什么 幂集 （S）？

如何 呢？

减少一组元素

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

S =（a，b），然后 幂集 （S）= {（），（a），（b），（a，b）}

什么不见​​了？

幂集 （S）= {（c），（a，c），（b，c），（a，b，c）}

嗯

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

幂集 （S）= {（），（a），（b），（c），（a，b），（a，c），（b，c），（a，b，c）}

取出任何元素

幂集 （S）= {（），（a），（b），（c），（a，b），（a，c），（b，c），（a，b，c）}

幂集 （S-{c}）= {（），（a），（b），（a，b）}与

{c} U 幂集 （S-{c}）= {（c），（a，c），（b，c），（a，b，c）}

幂集 （S）= 幂集 （S-{e i }）U（{e i } U 幂集 （S-{e i }））

其中e i是S的元素（单例）

伪算法

  1. 传递的集是否为空？完成（请注意，{}的幂集为{{}}）

  2. 如果没有，取出一个元素

    • 在集合的其余部分上递归调用方法

    • 返回由联合组成的集合

    • 没有元素的集合的幂集（来自递归调用）

    • 同一组（即 2.1 ），但其中的每个元素都与最初取出的元素结合在一起

以上是 哪种算法可以计算给定集合的幂集？ 的全部内容， 来源链接： utcz.com/qa/414470.html

回到顶部