I am asking this question to avoid reinventing the wheel (also because I am lazy). I have to arrays of integers in normal order with no repeats within each array. Then I generate an array by concatenation the two arrays. This array can have out of order elements and can have repeated elements. For example

[1,3,4][2,3,5] => [1,3,4,2,3,5]

How many exchanges to get [1,2,3,3,4,5]?

Do you have any suggestions or links before I start using brute force.

Here is a related problem. Consider the following rules for exchanging elements of an array - [a_1,â€¦,a_i,a_(i+1),â€¦,a_n]

If a_i == a_(i+1) then

[a_1,â€¦,a_i,a_(i+1),â€¦,a_n] => g(a_i,a_i)[a_1,â€¦,a_(i-1),a_(i+2),â€¦,a_n]

where the g(a_i,a_i) is a coefficient associated with the reduced array.

If a_i != a_(i+1) then

[a_1,â€¦,a_i,a_(i+1),â€¦,a_n] => 2g(a_i,a_(i+1)) [a_1,â€¦,a_(i-1),a_(i+2),â€¦,a_n]

-[a_1,â€¦,a_(i+1),a_i,â€¦,a_n]

Again the 2g(i,i=1) and -1 are coefficients associated with the arrays (think of each array as a basis vector). The objective is to take the array [a_1,â€¦,a_i,a_(i+1),â€¦,a_n] and reduce it to a linear combination of coefficients and arrays where each array is in normal order with no repeated elements.