2

n 個の配列の配列があり、すべてサイズが異なる可能性があります。各配列から 1 つだけの値を使用して 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)と、サブ配列の一意のペアがすべて出力されます。配列のペアごとに、最初の配列のすべての要素が 2 番目の配列のすべての要素と一致します (デカルト積を参照)。

flat_map配列の配列の配列を取得することを避けるためにここにあります。

サイズ

組み合わせの使用

式は 3 つのサブ配列に対して正しいです。配列の場合n、2 つのサブ配列のすべての組み合わせをリストし、それぞれのサイズの積を合計する必要があります。

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 に答える