class ComboFinder

def cache_result result, data, cache # :nodoc:
  cache[data] = true
  return result if result
  unless result or data.size > 128 then
    max = data.size
    subdiv = 2
    until subdiv >= max do
      data.each_slice(max / subdiv) do |sub_data|
        cache[sub_data] = true
      end
      subdiv *= 2
    end
  end
  result
end

def d s = "" # :nodoc:
  warn s if ENV["MTB_DEBUG"]
end

def find_minimal_combination ary
  level, n_combos = 1, 1
  seen = {}
  d "Total number of culprits: #{ary.size}"
  loop do
    size = 2 ** (Math.log(ary.size) / Math.log(2)).round
    divs = 2 ** level
    done = divs >= size
    divs = size if done
    subsections = ary.each_slice(size/divs).to_a.combination(n_combos)
    d
    d "# new round!"
    d "#   of subsections in this round: #{subsections.to_a.size}"
    d
    found = subsections.find { |a|
      b = a.flatten
      next if seen[b]
      d "#   trying #{b.size} at level #{level} / combo #{n_combos}"
      cache_result yield(b), b, seen
    }
    if found then
      ary = found.flatten
      break if done
      seen.delete ary
      d "#   FOUND!"
      d "#     search space size = #{ary.size}"
      d "#     resetting level and n_combos to 1"
      level = n_combos = 1
    else
      if done then
        n_combos += 1
        d "#   increasing n_combos to #{n_combos}"
        break if n_combos > size
      else
        level += 1
        n_combos = level
        d "#   setting level to #{level} and n_combos to #{n_combos}"
      end
    end
  end
  ary
end