Instantly share code, notes, and snippets.

# JEG2/what_am_i.md

Created February 19, 2014 00:49
Show Gist options
• Save JEG2/9084019 to your computer and use it in GitHub Desktop.

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.

### csuhta commented Feb 19, 2014

I'm not exactly sure what you're asking here. Do you want to insert the items into `results` in-place or already in order somehow? Do you feel that you should be able to combine the collections more efficiently somehow? Are you looking for the name of a specific sorting algorithm that might be useful here?

BTW, it's faster if you use `results.sort_by!(&:last)`, right?

```require "benchmark"

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

Benchmark.bm do |x|
x.report {
results = [ ]
a.each do |i|
b.each do |j|
results << [i, j, i + j]
end
end
results.sort_by!(&:reverse)
}
x.report {
results = [ ]
a.each do |i|
b.each do |j|
results << [i, j, i + j]
end
end
results.sort_by!(&:last)
}
end

#=>      real
#=> (0.000026)
#=> (0.000011)```

### JEG2 commented Feb 19, 2014

I want to know if I can add them to results already sorted, yes.

### jah2488 commented Feb 19, 2014

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)```

### csuhta commented Feb 19, 2014

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

### JEG2 commented Feb 19, 2014

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

to join this conversation on GitHub. Already have an account? Sign in to comment