this is a follow-up question to Determine if two unsorted arrays are identical?

Given two unsorted arrays A and B with the same number of distinct elements (positive integers>0), determine if A and B can be rearranged so that they are identical.

I don't want to actually rearrange the elements, just perform a quick and inexpensive check if it is possible (I need to perform this on a large number of such arrays).

I was thinking about a check based on the sum and product of the elements. I.e., if 1. and 2. are true, A and B can be rearranged so that they are identical:

1. a_1 a_2 ... a_n = b_1 b_2 ... b_n
2. a_1*a_2*...*a_n = b_1*b_2*...*b_n

However, the mathematical foundations of this approach seem shaky to me. Are there similar proofs, which are mathematically more rigorous?

CodePudding user response：

By The Vieta formulas, the sum and the product of n numbers are the second and last coefficients of a polynomial having those numbers for roots (to a change of sign). The other coefficients remain free, leaving many possibilities for distinct numbers.

E.g. sum = 3, product = 4.

The polynomial x³-3x²-21x-4 has the roots -3.19, -0.19634, 6.3863.

The polynomial x³-3x²-12x-4 has the roots -2, -0.37228, 5.3723.

These two distinct triples have the desired properties.

Addendum:

Comparing all coefficients of the expansion of (x-a)(x-b)...(x-z), which are known as the elementary symmetric polynomials (a b ...z, ab bc ...za, abc bcd ...zab, ..., ab..z) is enough to prove equality of the roots, whatever the order. But I would not recommend this very costly method.