Here are two other approaches.
#1
You could use methods from the Matrix
class:
require 'matrix'
def unique_products(r)
a = [*r]
(Matrix::column_vector(a) * Matrix::row_vector(a)).to_a.flatten.uniq
end
unique_products((1..4))
#=> [1, 2, 3, 4, 6, 8, 9, 12, 16]
The class methods Matrix::column_vector and Matrix::row_vector are used to convert r1
to a column vector and r2
to a row vector. Matrix#* is then used to compute the outer product, a matrix that contains the products of all pairs of elements from the two ranges. That matrix is then converted to an array, flattened and uniq
'ed, to eliminate duplicates.
Compared to approaches that do not use matrix methods, this one has some extra steps and greater memory requirements. However, the computation of the outer product, being implemented in C, should be relatively fast. Whether this method is faster than other methods is an empirical question. (Edit: the benchmark showed this method to be relatively slow.)
#2
The second approach employs a bit of fine tuning to boost performance:
def cary2(r)
f, l = r.first, r.last
fpl = f+l
m = fpl/2
ml = m+1
mf = fpl.odd? ? m : m-1
arr = (f..mf).each_with_object([]) { |i,a| p = i*fpl;
(i..mf).each { |j| n = i*j; a << n << p-n } }
(ml..l).each { |i| p = i*fpl;
(ml..i).each { |j| n = i*j; arr << n << p-n } }
if (fpl).even?
p = m*fpl
(f..mf).each { |i| n = i*m; arr << n << p-n }
arr << m*m
end
arr.uniq
end
Let f
and l
be the range endpoints, and let m
be the average:
m = (f+l)/2
There are two cases to consider, depending on whether f+l
is even or odd. The easier of the two is when it is odd. Suppose, for example, f=1
and l=6
, so m=3
and f+l
is odd. In this case the range can be divided into (1..3)
and (4..6)
. Let a
be the array that will hold the products. When calculating:
(1..3).each { |i| (i..3).each { |j| a << i*j }
we can also calculate:
(1..3).each { |i| (i..3).each { |j| a << i*(l-(j-f)) }
which is:
(1..3).each { |i| (i..3).each { |j| a << i*(f+l) - i*j }
We can combine these as follows:
fpl = f+l
(1..3).each { |i| p = i*fpl; (i..3).each { |j| n = i*j; a << n << p-n }
Similarly, for
(4..6).each { |i| (4..i).each { |j| a << i*j }
we can also calculate:
(4..6).each { |i| (4..i).each { |j| a << i*(f+(l-j) }
which is:
(4..6).each { |i| (4..i).each { |j| a << i*(f+l) - i*j }
so we can write:
(4..6).each { |i| p = i*fpl; (4..i).each { |j| n = i*j; a << n << p-n }
These two expressions cover all the products.
If f+l
is even, the situation is slightly more complex. Suppose f=1
and l=5
, so f+l = 6
and m = 3
. In this case we will perform the same calculations as above, but for (1..2)
and (4..5)
. We must then add the combinations involving the midpoint, 3
. An efficient way to do this is as follows:
p = 3*(1+5)
(1..2).each { |i| n = i*3; arr << n << p-n }
arr << 3*3