Created
June 24, 2014 13:40
-
-
Save jopotts/0e250d1280ea838a5faa to your computer and use it in GitHub Desktop.
Find combinations of sets built from a range that add to a given value
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class SetPartitioner | |
| def initialize(min, max, total) | |
| @min = min | |
| @max = max | |
| @total = total | |
| end | |
| def any? | |
| sets.present? | |
| end | |
| def sets | |
| @sets ||= get_sets | |
| end | |
| def optimal_set | |
| sets.min_by { |s| s.length }.reverse | |
| end | |
| private | |
| def get_sets | |
| Timeout::timeout(3) do | |
| max_group_size = (@total / @min.to_f).ceil | |
| range = (@min..@max).to_a | |
| all_options = ([range] * max_group_size).flatten.sort.reverse | |
| sets = subsets_with_sum(all_options) | |
| sets = sets.map { |r| r.sort }.uniq | |
| sets.sort | |
| end | |
| rescue Timeout::Error | |
| raise "Timeout in SetPartitioner: #{@min}-#{@max} into #{@total}." | |
| end | |
| def subsets_with_sum(numbers, partial=[]) | |
| result = [] | |
| sum = partial.inject(0, :+) | |
| if sum == @total | |
| result << partial | |
| elsif sum < @total | |
| (0..(numbers.length - 1)).each do |i| | |
| n = numbers[i] | |
| remaining = numbers.drop(i + 1) | |
| result += subsets_with_sum(remaining, partial + [n]) | |
| break unless result.blank? # return only the first | |
| end | |
| end | |
| result | |
| end | |
| end |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'test_helper' | |
| class SetPartitionerTest < ActiveSupport::TestCase | |
| test "normal" do | |
| sp = SetPartitioner.new(3, 5, 12) | |
| # assert_equal [[3, 3, 3, 3], [3, 4, 5], [4, 4, 4]], sp.sets | |
| assert_equal [5, 4, 3], sp.optimal_set | |
| assert sp.any? | |
| end | |
| test "empty" do | |
| sp = SetPartitioner.new(12, 15, 35) | |
| refute sp.any? | |
| end | |
| test "big set" do | |
| sp = SetPartitioner.new(5, 9, 66) | |
| assert_equal [9, 9, 9, 9, 9, 9, 7, 5], sp.optimal_set | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
With a little help from here: http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum
Remove
break unless result.blank?on line 46 to return all sets. Left in as onlyoptimal_setrequired and speeds it up a lot.