arrays - Ruby 不同大小的 n 个数组中 2 个的唯一组合

Question

我有一个由 n 个数组组成的数组，所有数组的大小都可能不同。我需要通过使用每个数组中不超过一个值来计算 2 的可能组合并打印总数。例如:

我有:

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

我想得到:

[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

在数学上，我认为这是 xy + xz + y*z 或:

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

如果我在公式上有误，请随时纠正我。

无论如何，对于未知的 n 个数组，我该如何实现？

Answer 1

数组

您可以使用 combination和笛卡尔 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

在数组上调用combination(2) 会输出所有唯一的子数组对。对于每对数组，第一个数组的每个元素都与第二个数组的每个元素匹配(参见 Cartesian product )。

flat_map这里是为了避免获取数组的数组。

大小

使用组合

您的公式对于 3 个子数组是正确的。对于n数组，你需要列出两个子数组的所有组合，然后将它们各自大小的乘积相加:

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

备选

利用 (x+y+z)**2 的扩展版本是

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

我们看到了:

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

所以

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

它看起来不像是 3 个值的快捷方式，但它推广到 n 数组，并帮助我们完全避免组合:

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