Algorithm to determine minimum of swaps to make two binary arrays identical

Question

Is there a known algorithm or formula to determine how many swaps are to make a binary array A look like B?

For example if:

 Array A =   [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 Array B =   [1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]

I took this example from here , it says that we need 10 swaps to make array B to be ordered like array A. How can we come up with such a number?

Also, it says that:

to get from the random state to the ideal state would take 6 x 9/2 flips (there are 6 bad and 9 goods)

How do we come with such a rule of ((number of zeros)*(number of ones)) / 2 To determine how many swaps it would take to operate from a random state?

EDIT:

What if the array A is more sparse? How do we determine the minimum number of swaps?

 Array A =   [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1]

Answer 1

Assuming that the "ideal state" is a state of the form

[1, 1, ..., 1, 0, 0, ..., 0]

then we can think of the process of turning an array into the ideal state as moving all the 1s to the left. If a particular 1 has $k$ 0s to its left, then we will need to do $k$ swaps where we swap that 1 with a 0 to its left.

In your example

Array B =   [1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]

The number of 0s to the left of each 1 is

Zero(B) =   [0, 0, -, 1, -, 2, 2, -, -, -, 5, -, -, -, -]

and so the total number of swaps needed to get to the ideal state is $1 + 2 + 2 + 5 = 10$. Any algorithm which doesn't do anything stupid (that is, any algorithm which only performs 0, 1 to 1, 0 swaps) will take this many steps.

In a random state, if there are $a$ 1s and $b$ 0s, then each 1 has an expected number of $\frac b2$ 0s to its right, and so by linearity of expectation, the total number of swaps is $a \cdot \frac b2 = \frac{ab}{2}$, which is the rule you're quoting.

---

If we were instead trying to get from Array B to something like

Array C =   [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]

then to compute the number of steps we should figure out the same quantity - the number of 0s to the left - for each 1 in the target Array C:

Zero(C) =   [0, -, -, 2, 2, 2, -, -, -, -, 6, -, -, 8, -]

Since it never makes sense to swap two adjacent 1s (that would accomplish nothing), we know that the $i^{\text{th}}$ 1 in Array B should become the $i^{\text{th}}$ 1 in Array C. If we compare these side by side (dropping the -s in the expressions above) we get

Zero*(B)=   [0, 0, 1, 2, 2, 5]
Zero*(C)=   [0, 2, 2, 2, 6, 8]

Then we know that, for example, the $5^{\text{th}}$ 1 should change from having $2$ 0s to its left to having $6$ 0s to its left, which means it should be swapped with a 0 $4$ times. Therefore the number of swaps necessary is just the sum of the absolute differences between the Zero* arrays: in this example,

$$|0-0| + |0-2| + |1-2| + |2-2| + |2-6| + |5-8| = 10.$$

This algorithm has the first algorithm as a special case, since if Array A had all its 1s before all its 0s then we'd have

Zero*(A)=   [0, 0, 0, 0, 0, 0]

so the sum of the absolute differences between the Zero* arrays is just the sum of the entries of Zero(B): the sum of the number of 0s to the left of each 1.