生成集合的powerset而不在Erlang或Ruby中保留堆栈

我想生成一个相当大的集合（约30-50个元素）的powerset，我知道它需要2^n来存储powerset。

是否有可能一次生成一个子集？

即生成具有迭代的集合的powerset，将每个生成的子集保存到磁盘/数据库，将其从堆栈/内存中删除，然后继续生成其他子集？

不幸的是，我没有根据我的需要修改Erlang和Ruby示例。

Answer 1

编辑：如果没有给出阻止，则添加枚举器（如@JörgWMittag）。

 class Array def powerset return to_enum(:powerset) unless block_given? 1.upto(self.size) do |n| self.combination(n).each{|i| yield i} end end end # demo ['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 10.times.map{ ps.next } # 10.times without a block is also an enumerator 

产量

 ["a"] ["b"] ["c"] ["a", "b"] ["a", "c"] ["b", "c"] ["a", "b", "c"] [[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 

Answer 2

生成列表的powerset（实际上是您的Erlang示例使用的那个）的一种方法是迭代所有数字x从0到2 ^ n（不包括），并且对于每个x ，生成包含i的列表当且仅当x第i位被设置时，原始列表的第th个元素。

由于使用此方法生成当前列表仅取决于x的值而不是任何先前生成的列表，因此在使用它们之后不必将列表保留在内存中。 所以这种方法可以用来做你想要的。

Answer 3

这使用标准的“位arrays”技巧来生成功率集（并且它使用Ruby的Integer表现为位数组的事实）。 但更重要的是，它使用Enumerator来懒惰地生成集合。

 require 'set' module Enumerable def powerset number_of_sets = 2 ** count Enumerator.new {|ps| number_of_sets.times {|i| ps << Set[*reject.with_index {|_, j| i[j].zero? }] } } end end 

即使对于数以千计的元素，这也完美无缺：

 enum = (1..10_000).powerset enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # enum.next # => # # ... 

编辑：这是基于@ steenslag的解决方案。 我完全忘记了Array#combination ，因为我过于专注于寻找适用于任何 Enumerable的解决方案。 但是，我的解决方案要求Enumerable无论如何都是有限的，并且任何有限的Enumerable都应该可以表示为一个Array ，所以这并不是一个限制。

 module Enumerable def powerset ary = to_a Enumerator.new {|ps| ary.size.times {|n| ary.combination(n).each(&ps.method(:yield)) } } end end