Generate a powerset of a set without keeping a stack in Erlang or Ruby

Question

I would like to generate a powerset of a rather big set (about 30-50 elements) and I know that it takes 2^n to store the powerset.

Is it possible to generate one subset at a time?

I.e. generate a powerset of a set with iterations, saving each generated subset to disk/database, removing it from the stack/memory and only then continuing to generate other subsets?

Unfortunately I have failed to modify Erlang and Ruby examples to my needs.

Antitoxic

Answer 1

Edit: Added the enumerator (as @Jörg W Mittag) if no block is given.

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]]

Illimani

Answer 2

One way to generate a powerset of a list (which is in fact the one that your Erlang example uses) is to iterate over all numbers x from 0 to 2^n (exclusive) and for each x, generate the list that contains the ith element of the original list if and only if the ith bit of x is set.

Since using this approach generating the current list only depends on the value of x and not on any of the previously generated lists, you don't have to keep the lists in memory after using them. So this approach can be used to do what you want.

Townie

I understand how to iterate over all number x from 2^n in Erlang, but I don't get the condition (I am not good at operations with bits). Could you be so kind to provide a simple example? – Antitoxic

@Martin: The condition is I band (1 bsl Pos) =/= 0 (taken from the Erlang code you linked). Actually you can just take the entire inner list from the code you linked, i.e. [lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0] (where I is the number you're iterating from 0 to 2^n). Though come to think of it, that's pretty inefficient in Erlang on account of lists:nth being O(n)... – Townie

Answer 3

This uses the standard "bit array" trick for generating power sets (and it uses the fact that Ruby's Integers behave as bit arrays). But more importantly, it uses an Enumerator to generate the 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 perfectly fine even for thousands of elements:

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 totally forgot about Array#combination, since I was too focused on finding a solution that would work for any Enumerable. However, my solution requires that the Enumerable be finite anyway, and any finite Enumerable should probably be representable as an Array, so that's not much of a restriction.

module Enumerable
  def powerset
    ary = to_a

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

Haphtarah

require 'set' not needed (anymore). – Illimani

You're right, of course. If you want to generate an actual power set as opposed to a "power array", you'd need to convert the combinations into sets before yielding them to the enumerator. – Loner

@JörgWMittag I can not make your code work, I can not actually understand it completely. – Berkly