123456789_123456789_123456789_123456789_123456789_

Class: ComboFinder

Relationships & Source Files
Inherits: Object
Defined in: lib/minitest/find_minimal_combination.rb

Overview

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

Instance Method Summary

Instance Method Details

#cache_result(result, data, cache)

This method is for internal use only.
[ GitHub ] 

  


# File 'lib/minitest/find_minimal_combination.rb', line 89



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


  








  

    #d(s = "")  
  

  

    This method is for internal use only.
  

  [ GitHub ]


  

  


# File 'lib/minitest/find_minimal_combination.rb', line 85



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


  








  

    #find_minimal_combination(ary)  
  



  

    

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.


  



  [ GitHub ]


  

  


# 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