Ruby Unique combinations of 2 from n arrays of different sizes

Question

I have an array of n arrays all potentially of different sizes. I need to calculate the possible combinations of 2 by using no more than one value from each array and print the total number. For example:

I have:

n = 3, in arr[n]
arr = [[0, 1], [2, 3, 4], [5, 6, 7, 8]]

I want to get:

[0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8],
[1, 8], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8],
[3, 5], [3, 6], [3, 7], [3, 8], 
[4, 5], [4, 6], [4, 7], [4, 8], etc.

return number of arrays

Mathematically, I believe this is xy + xz + y*z or:

arr[0].size * arr[1].size + arr[0].size * arr[2].size + arr[1].size * arr[2].size

Feel free to correct me if I'm mistaken on that formula.

Anyways, how can I achieve this for an unknown n arrays?

Answer 1

Arrays

You can use combination and Cartesian product :

arrays = [[0, 1], [2, 3, 4], [5, 6, 7, 8]]

p arrays.combination(2).flat_map{ |a, b| a.product(b) }.sort
#=> [[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [0, 5], [0, 6], [0, 7], [0, 8], [1, 5], [1, 6], [1, 7], [1, 8], [2, 5], [2, 6], [2, 7], [2, 8], [3, 5], [3, 6], [3, 7], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8]]

p arrays.combination(2).flat_map{ |a, b| a.product(b) }.sort
#=> [[0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 5], [2, 6], [2, 7], [2, 8], [3, 5], [3, 6], [3, 7], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8]]

p arrays.combination(2).flat_map{|a,b| a.product(b)}.size
#=> 26

Calling combination(2) on the array outputs all the unique pairs of sub-arrays. For each pair of arrays, every element of the first array is matched with every element of the second array (see Cartesian product).

flat_map is here to avoid getting an array of arrays of arrays.

Size

Using combinations

Your formula is correct for 3 sub-arrays. For n arrays, you need to list all the combinations of two sub-arrays, and sum the product of their respective size :

p arrays.map(&:size).combination(2).map{|s1, s2| s1*s2}.inject(:+)
#=> 26

Alternative

Using the fact that the expanded version of (x+y+z)**2 is

x**2 + 2*xy + y**2 + 2*xz + 2*yz + z**2

we see that :

2*xy + 2*xz + 2*yz = (x+y+z)**2 - (x**2 + y**2 + z**2)

so

xy + xz + yz = ( (x+y+z)**2 - (x**2 + y**2 + z**2) )/2

It doesn't look like much of a shortcut for 3 values, but it generalizes to n arrays, and helps us avoid combination altogether :

sizes = arrays.map(&:size)
p (sizes.inject(:+)**2 - sizes.map{|s| s**2}.inject(:+))/2
#=> 26