Генерация набора мощности набора без сохранения стека в Erlang или Ruby

Question

Я хотел бы сгенерировать powerset довольно большого набора (около 30-50 элементов), и я знаю, что это занимает 2^n хранить 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

Один из способов создания powerset списка (который фактически является тем, который использует ваш пример Erlang), состоит в том, чтобы перебрать все числа x от 0 до 2^n (исключая) и для каждого xсоздать список, содержащий iй элемент исходного списка, если и только если iй бит x установлено.

Поскольку при использовании этого подхода создание текущего списка зависит только от значения 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