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

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

4 голосов
/ 16 декабря 2011

Я хотел бы сгенерировать блок питания из довольно большого набора (около 30-50 элементов), и я знаю, что для хранения блока питания требуется 2^n.

Можно ли сгенерировать одно подмножество ввремя?

Т.е. генерировать набор мощности набора с итерациями, сохраняя каждое сгенерированное подмножество на диск / базу данных, удаляя его из стека / памяти и только затем продолжая генерировать другие подмножества?

К сожалению, мне не удалось изменить Erlang и Ruby примеров для моих нужд.

Ответы [ 3 ]

5 голосов
/ 16 декабря 2011

Редактировать: Добавлен перечислитель (как @ 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]]
5 голосов
/ 16 декабря 2011

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

Поскольку при использовании этого подхода генерация текущего списка зависит толькозначение x и не указано ни в одном из ранее созданных списков, вам не нужно хранить списки в памяти после их использования.Так что этот подход можно использовать, чтобы делать то, что вы хотите.

1 голос
/ 16 декабря 2011

Используется стандартный трюк "битовый массив" для генерации наборов мощности (и тот факт, что Integer в Ruby ведут себя как битовые массивы).Но что еще более важно, он использует 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
...