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

Question

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

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

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

不幸的是，我未能根据我的需要修改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 示例使用的）的一种方法是遍历x从 0 到 2^n （不包括）的所有数字，并为每个x生成包含第ith 元素的列表当且仅当ith 位x被设置时，原始列表。

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

Answer 3

Integer这使用标准的“位数组”技巧来生成幂集（并且它使用 Ruby 的s 表现为位数组这一事实）。但更重要的是，它使用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人都有效的解决方案。但是，我的解决方案无论如何都要求是有限的，并且任何有限都应该可以表示为，所以这不是太大的限制。 EnumerableEnumerableEnumerableArray

module Enumerable
  def powerset
    ary = to_a

    Enumerator.new {|ps|
      ary.size.times {|n|
        ary.combination(n).each(&ps.method(:yield))
      }
    }
  end
end