0

I need to create a combination of sum of values closest to the target value. The combination needs to be of x numbers, where x is defined by the user. The algorithm will output the combination closest to a target value entered by the user. I also need to display the keys (values) that the algorithm returns.

Here is how I think the algorithm will work:

Target: 575

Values with corresponding keys:

150 [0] | 75 [1] | 123 [2] | 212 [3] | 23 [4] | 89 [5] | 20 [6]

77 [7] | 39 [8] | 16 [9] | 347 [10] | 512 [11] | 175 [12]

User wants Groups of: 5 values

The algorithm now runs combinations of sum of 5 values on the whole set and returns a sum of the values closest to the target value of 575.

Result

150 [0] + 212 [3] + 23 [4] + 77 [7] + 89 [5] = 551

Keys used were 0, 3, 4, 7, and 5.

I could use Arrays#combination(n), but I will not be able to keep track of the keys. I have been able to come up with a Hash which stores "key" => "int values", but I have no idea how to come up with an optimized algorithm to combine values stored in a Hash.

{0=>"150"}
{1=>"212"}
{2=>"23"}
{3=>"77"}
{4=>"89"}

P.S. This is not a homework. Its a personal project to put on the resume, talk about at interviews, and to learn to convert my ideas to code.

lkapoor
  • 31
  • 5
  • Are you sure you want to deal with `a combination of sum of values`? So you prepare a combination of combinations of numbers, and calculate the sum for each combination? And, `combination [of numbers] closest to a target (number) value` does not make sense. How can a combination (probably an array) be "closest" in any sense to a number? – sawa Sep 20 '13 at 06:50
  • Its a sum of combinations. Sum of say any X values from the set closest to the target. – lkapoor Sep 20 '13 at 07:04
  • Can you perdict how many elements there are in every array? If there are only few elements like shown above, a simple brute-force approach might be just the way to go. – Patrick Oscity Sep 20 '13 at 07:07
  • That depends on the user input. If the user can request a sum of 10 or 100 values that make a value closes to the target. – lkapoor Sep 20 '13 at 07:27

2 Answers2

1

In order to keep track of the indice, you can apply combination on the indice of the array, not the array itself.

array = [150, 75, 212, 23, 89, 20, 77, 39, 16, 347, 512, 175]
target = 575
x = 5

closest_indice =
array
.each_index.to_a
.combination(x)
.min_by{|is| (array.values_at(*is).inject(:+) - target).abs}

However, the answer is different from what you claim:

closest_indice # => [0, 3, 7, 8, 9]
array.values_at(*closest_indice) # => [150, 23, 39, 16, 347]
array.values_at(*closest_indice).inject(:+) # => 575

and I don't understand why you have a different answer.

Edit

As noticed my Stefan, there is no index 2. To deal with that:

hash = {0 => 150, 1 => 75, 3 => 212, 4 => 23, 5 => 89, 6 => 20, 7 => 77, 8 => 39, 9 => 16, 10 => 347, 11 => 512, 12 => 175}
target = 575
x = 5

closest_keys =
hash
.keys
.combination(x)
.min_by{|is| (hash.values_at(*is).inject(:+) - target).abs}

closest_keys # => [0, 4, 8, 9, 10]
hash.values_at(*closest_indice) # => [150, 23, 39, 16, 347]
hash.values_at(*closest_indice).inject(:+) # => 575

Notice This answer applies to the question as was at the beginning (i.e., before the OP changed the question to add an element 123 with index 2).

sawa
  • 165,429
  • 45
  • 277
  • 381
1

Something like this would work:

hash = {0 => 150, 1 => 75, 2 => 123, 3 => 212, 4 => 23, 5 => 89, 6 => 20, 7 => 77, 8 => 39, 9 => 16, 10 => 347, 11 => 512, 12 => 175}

# all key combinations of length 5
keys_of_5 = hash.keys.combination(5)
#=> #<Enumerator: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12]:combination(5)>
#   i.e. [[0, 1, 2, 3, 4], [0, 1, 2, 3, 5], [0, 1, 2, 3, 6], ...]

# sum the values for each combination
sums_of_5 = keys_of_5.map { |keys| [keys, hash.values_at(*keys).inject(:+)] }
#=> [[[0, 1, 2, 3, 4], 583], [[0, 1, 2, 3, 5], 649], [[0, 1, 2, 3, 6], 580], ...]

# sort by distance to target
sorted = sums_of_5.sort_by { |keys, sum| (sum - 575).abs }
#=> [[[4, 5, 7, 8, 10], 575], [[0, 4, 8, 9, 10], 575], [[3, 4, 5, 7, 12], 576], ...]

# let's find the nearest ones
nearest = sorted.select { |keys, sum| sum == sorted.first[1] }

# and print 'em
nearest.each do |keys, sum|
  puts keys.map { |key| "%3d [%d]" % [hash[key], key] }.join(" + ") << " = #{sum}"
end

Output

 23 [4] +  89 [5] +  77 [7] +  39 [8] + 347 [10] = 575
150 [0] +  23 [4] +  39 [8] +  16 [9] + 347 [10] = 575
Stefan
  • 109,145
  • 14
  • 143
  • 218
  • `min_by {}` is equivalent to `sort {}.first` (and nicer to read IMO) – Neil Slater Sep 20 '13 at 07:31
  • The former is more efficient. – sawa Sep 20 '13 at 07:38
  • @Stefan Watch out. The OP changed the question. But anyway, your sum is different from mine, and that should not depend on the way key/index are given. I wonder what is wrong. – sawa Sep 20 '13 at 07:39
  • Sorry about that guys. I did not think the indexes would matter to understand the logic, but it apparently does since you all are actually testing with the numbers, – lkapoor Sep 20 '13 at 07:41
  • I've updated my answer to reflect the OP's edit and fixed a bug along the way. – Stefan Sep 20 '13 at 07:43
  • @Stefan: At step 2 (keys_of_5 = ...) it returns `=> #` instead of what you posted. Any idea why? – lkapoor Sep 20 '13 at 07:58
  • I've posted the result for `keys_of_5.to_a`, updated my answer – Stefan Sep 20 '13 at 08:02
  • @NeilSlater right, but as it turn out, there can be more than one result and there's no `mins_by` to return all of them. – Stefan Sep 20 '13 at 08:08