class Array
  def powerset
    num = 2**size
    ps = Array.new(num, [])
    self.each_index do |i|
      a = 2**i
      b = 2**(i+1) - 1
      j=0
      while j < num-1
        for j in j+a..j+b
          ps[j] += [self[i]]
        end
        j += 1
      end
    end
    ps
  end
end

x = [1, 2, 3]
y = x.powerset
# y is now:
#   [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

