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

Question

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

是否可以一次生成一个子集？

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

不幸的是，我未能修改 Erlang 和 Ruby 满足我的需求的示例。

Answer 1

编辑：如果没有给出块，则添加枚举器（如@Jörg W Mittag）。

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

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

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

Answer 3

它使用标准的“位数组”技巧来生成幂集（并且它使用了 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 # => #<Set: {}>
enum.next # => #<Set: {1}>
enum.next # => #<Set: {2}>
enum.next # => #<Set: {1, 2}>
enum.next # => #<Set: {3}>
enum.next # => #<Set: {1, 3}>
enum.next # => #<Set: {2, 3}>
enum.next # => #<Set: {1, 2, 3}>
enum.next # => #<Set: {4}>
enum.next # => #<Set: {1, 4}>
enum.next # => #<Set: {2, 4}>
enum.next # => #<Set: {1, 2, 4}>
enum.next # => #<Set: {3, 4}>
enum.next # => #<Set: {1, 3, 4}>
enum.next # => #<Set: {2, 3, 4}>
enum.next # => #<Set: {1, 2, 3, 4}>
enum.next # => #<Set: {5}>
# ...

编辑：这是基于@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