john_lynch_scrtip

partitions.cr

def get_partition_original(ss)
    return (ss.size == 0 ? [[[] of Int32]] : [[ss]]) if ss.size <= 1
    out = [[Array(Int32).new, Array(Int32).new]].clear
    (0...2**ss.size / 2).each { |i|
        parts = [Array(Int32).new, Array(Int32).new]
        ss.each { |item|
            parts[i&1] << item
            i >>= 1
        }
        get_partition_original(parts[1]).each { |b|
            out << (b[0].empty? ? [parts[0]] : [parts[0]] + b)
        }
    }
    out
end

def get_partition(ss)
  return (ss.size == 0 ? [[[] of Int32]] : [[ss]]) if ss.size <= 1
  out = [] of Array(Array(Int32))

  (0...2**ss.size / 2).each do |i|
    parts = [[] of Int32, [] of Int32]
    ss.each do |item|
      parts[i&1] << item
      i >>= 1
    end
    get_partition(parts[1]).each do |b|
      out << (b[0].empty? ? [parts[0]] : [parts[0]] + b)
    end
  end
  out
end

require "benchmark"

part = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Benchmark.ips do |x|
  x.report("original implementation") { get_partition_original(part) }
  x.report("new implementation") { get_partition(part) }
end