Create a set of set parameters without saving a stack in Erlang or Ruby

Question

I would like to create a set of a fairly large set (about 30-50 elements), and I know that it takes 2^n to store a set of parameters.

Is it possible to generate one subset at a time?

those. generate a parameter set with iterations, saving each generated subset to disk / database, deleting it from the stack / memory, and only then continuing to generate other subsets?

Unfortunately, I was unable to modify Erlang and Ruby for my needs.

Answer 1

Edit: Added enumerator (like @ Jörg W Mittag) if block is not specified.

 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 

Output

 ["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

One way to generate a set of list parameters (actually the one used by your Erlang example) is to iterate over all numbers x from 0 to 2 ^ n (excluding) and for each x generate a list containing the element i th of the source list if and only if i th bit x .

Since using this approach, generating the current list depends only on the value of x , and not on any of the previously generated lists, you do not need to save the lists in memory after using them. Thus, this approach can be used to do what you want.

Answer 3

It uses the standard bit-array trick to generate power sets (and it uses the fact that Ruby Integer behaves like bit-arrays). But more importantly, it uses the Enumerator to generate sets lazily.

 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 

This works great even for thousands of items:

 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}> # ... 

EDIT: This is based on @steenslag's solution. I completely forgot about Array#combination , as I was too focused on finding a solution that would work for any Enumerable . However, my solution requires that Enumerable be finite anyway, and any finite Enumerable should probably be representable as Array , so that is not much of a limitation.

 module Enumerable def powerset ary = to_a Enumerator.new {|ps| ary.size.times {|n| ary.combination(n).each(&ps.method(:yield)) } } end end