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

Question

我想生成一个相当大的集合(约30-50个元素)2^n的powerset ,我知道它需要存储powerset.

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

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

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

Answer 1

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

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

Answer 2

编辑:如果没有给出阻止,则添加枚举器(如@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]]