什么算法可以计算给定集的功率集？

Question

我想基于数字的起始列表有效地生成唯一的数字组合列表.

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

Answer 1

算了算0来2^n - 1,并根据您的计数的二进制表示打印的数字.a 1表示打印该编号,0表示不打印.例:

set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
        00011 => print {1, 2}
        00100 => print {3}
        00101 => print {1, 3}
        00110 => print {2, 3}
        00111 => print {1, 2, 3}
        ...
        11111 => print {1, 2, 3, 4, 5}

Answer 2

你要问的是一个名字.它被称为动力装置.

谷歌搜索"功率集算法"让我得到了这个递归解决方案.

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)则则powerset(S)是所有子集的集合, 其中(S)= {(),(a),(b),(c),(a,b),( a,c),(b,c),(a,b,c)}

第一个"技巧"是尝试递归定义.

什么是停止状态？

S =()有什么powerset(S)？

怎么做到的？

减少一个元素的设置

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

S =(a,b)然后 powerset(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 - {e _i })U({e _i } U powerset(S - {e _i }))

其中e _i是S的元素(单身)

伪算法

1. 套装是否空了？完成(注意{}的幂集是{{}})
2. 如果没有,请取出一个元素
   • 在集合的其余部分递归调用方法
   • 返回由联盟组成的集合
     1. 没有元素的集合的powerset(来自递归调用)
     2. 同一组(即2.1),但其中的每个元素与最初取出的元素联合

Answer 3

def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end