I'm trying to solve or at least learn more about this problem.

what_am_i.md

I have a problem that pretty much boils down to this:

a = [1, 2, 3]
b = [1.1, 2.2, 3.3]

# BEGIN GROSS SOLUTION:  avert your eyes!
results = [ ]
a.each do |i|
  b.each do |j|
    results << [i, j, i + j]
  end
end
results.sort_by!(&:reverse)
# END GROSS SOLUTION

results.each do |row|
  p row
end
# >> [1, 1.1, 2.1]
# >> [2, 1.1, 3.1]
# >> [1, 2.2, 3.2]
# >> [3, 1.1, 4.1]
# >> [2, 2.2, 4.2]
# >> [1, 3.3, 4.3]
# >> [3, 2.2, 5.2]
# >> [2, 3.3, 5.3]
# >> [3, 3.3, 6.3]

As my gross solution hopefully shows, I want to combine these items into a list ordered by the cheapest combinations as efficiently as possible. I know the lists are sorted going into the challenge. I need to do this in the most efficient manner possible.

Is this a famous problem with a name? I feel like I should recognize it, but I don't.

Thanks in advance for any context you can provide.

I want to say you're right and that there is some named problem underlying this, but I can't think of what it is either. My first thought was that maybe this has something to do with permutations and combinations, but couldn't find anyway to easily apply those in ruby. At least not with the permutation and combination methods defined on Array.

Maybe I'll keep looking into it. In the mean time, you could certainly make that code a little bit shorter.

a.flat_map { |x| b.map { |z| [x,z,x+z] } }.sort_by(&:last) #yay no mutated local state

Leveraging the block syntax of Array#product you can come with something like this.

c = []; a.product(b) { |x, z| c << [x, z, x + z] }; c.sort_by(&:last)

           user     system      total        real
#original :  0.000000   0.000000   0.000000 (  0.000135)
#    last :  0.000000   0.000000   0.000000 (  0.000087)
#flat_map :  0.000000   0.000000   0.000000 (  0.000059)
# product :  0.000000   0.000000   0.000000 (  0.000088)

Kind of grasping here, but perhaps you're looking to use a Heap to store the results?

I was looking for this problem: Sorting X + Y/Pairwise Sums.