class ComboFinder

Finds the minimal combination of a collection of items that satisfy test.

Public Instance Methods

find_minimal_combination(ary) { |b| ... } click to toggle source

Find the minimal combination of a collection of items that satisfy test.

If you think of the collection as a binary tree, this algorithm does a breadth first search of the combinations that satisfy test.

# File lib/minitest/find_minimal_combination.rb, line 30
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