2

我有一个由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

在数学上，我相信这是 x y + x z + y*z 或：

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

如果我对该公式有误，请随时纠正我。

无论如何，我怎样才能为未知的n数组实现这一点？

4

1 回答 1

3

数组

您可以使用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)数组输出所有唯一的子数组对。对于每对数组，第一个数组的每个元素都与第二个数组的每个元素匹配（请参阅笛卡尔积）。

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数组，并帮助我们combination完全避免：

sizes = arrays.map(&:size)
p (sizes.inject(:+)**2 - sizes.map{|s| s**2}.inject(:+))/2
#=> 26
于 2017-01-11T19:11:42.923 回答