Different ways of generating subsets of a Ruby array

subsets.rb

require 'benchmark'
require 'test/unit'

class Array

  def map_with_index
    ary = []
    each_with_index { |elt, i| ary << yield(elt, i) }
    ary
  end
  
  def subsets_0
    if empty?
      [[]]
    else
      first   = self[0]
      rest    = self[1..-1]
      recurse = rest.subsets_0
      
      recurse + recurse.map { |s| s << first }
    end
  end
  
  def subsets_1
    if empty?
      [[]]
    else
      first = self[0]
      rest  = self[1..-1]
      
      rest.subsets_1 + rest.subsets_1.map { |s| s << first }
    end
  end
  
  def subsets_2
    l = 2**length
    
    (0...l).map do |i|
      bit = 1
      idx = 0
      ary = []      
      
      while bit < l
        ary << self[idx] if i & bit > 0
        
        bit <<= 1
        idx += 1
      end
      
      ary
    end
  end
  
  def subsets_3
    l = 2**length
    
    (0...l).map do |i|
      str = i.to_s(2).split ''
      
      str.map_with_index { |e, idx| e == '1' ? self[idx] : nil }.compact
    end
  end
  
end

class SubsetTest < Test::Unit::TestCase

  # def test_subsets_of_the_empty_set_is_the_empty_set
  #   assert_equal [[]], [].subsets
  # end
  # 
  # def test_subsets_of_single_element_set
  #   assert_equal [[], [:a]], [:a].subsets_3
  # end
  # 
  # def test_subsets_of_a_three_element_set_should_have_8_elements
  #   assert_equal 8, [:a, :b, :c].subsets_3.length
  # end
  
end

SET = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

# puts 1234.to_s(2).split('').map_with_index { |e, i| i if e == '1' }.compact.inspect

Benchmark.bmbm do |x|

  x.report("recursive") { SET.subsets_0 }  
  x.report("recursive") { SET.subsets_1 }
  x.report("linear")    { SET.subsets_2 }
  x.report("linear")    { SET.subsets_3 }
  
end