Minimal number of swaps?

Question

There are N characters in a string of types A and B in the array (same amount of each type). What is the minimal number of swaps to make sure that no two adjacent chars are same if we can only swap two adjacent characters ? For example, input is:

AAAABBBB

The minimal number of swaps is 6 to make the array ABABABAB. But how would you solve it for any kind of input ? I can only think of O(N^2) solution. Maybe some kind of sort ?

Answer 1

I think this answer is similar to the answer by phs, just in Haskell. The idea is that the resultant-indices for A's (or B's) are known so all we need to do is calculate how far each starting index has to move and sum the total.

Haskell code:

Prelude Data.List> let is = elemIndices 'B' "AAAABBBB" 
                   in minimum 
                   $ map (sum . zipWith ((abs .) . (-)) is) [[1,3..],[0,2..]]
6 --output

Answer 2

If we need just to count swaps, then we can do it with O(N).

Let's assume for simplicity that array X of N elements should become ABAB... .

GetCount()
    swaps = 0, i = -1, j = -1
    for(k = 0; k < N; k++)
        if(k % 2 == 0)
            i = FindIndexOf(A, max(k, i))
            X[k] <-> X[i]
            swaps += i - k
        else
            j = FindIndexOf(B, max(k, j))
            X[k] <-> X[j]
            swaps += j - k
    return swaps

FindIndexOf(element, index)
    while(index < N)
        if(X[index] == element) return index
        index++
    return -1; // should never happen if count of As == count of Bs

Basically, we run from left to right, and if a misplaced element is found, it gets exchanged with the correct element (e.g. abBbbbA** --> abAbbbB**) in O(1). At the same time swaps are counted as if the sequence of adjacent elements would be swapped instead. Variables i and j are used to cache indices of next A and B respectively, to make sure that all calls together of FindIndexOf are done in O(N).

If we need to sort by swaps then we cannot do better than O(N^2).

The rough idea is the following. Let's consider your sample: AAAABBBB. One of Bs needs O(N) swaps to get to the A B ... position, another B needs O(N) to get to A B A B ... position, etc. So we get O(N^2) at the end.

Answer 3

@Nemo and @AlexD are right. The algorithm is order n^2. @Nemo misunderstood that we are looking for a reordering where two adjacent characters are not the same, so we can not use that if A is after B they are out of order.

Lets see the minimum number of swaps.

We dont care if our first character is A or B, because we can apply the same algorithm but using A instead of B and viceversa everywhere. So lets assume that the length of the word WORD_N is 2N, with N As and N Bs, starting with an A. (I am using length 2N to simplify the calculations).

What we will do is try to move the next B right to this A, without taking care of the positions of the other characters, because then we will have reduce the problem to reorder a new word WORD_{N-1}. Lets also assume that the next B is not just after A if the word has more that 2 characters, because then the first step is done and we reduce the problem to the next set of characters, WORD_{N-1}.

The next B should be as far as possible to be in the worst case, so it is after half of the word, so we need $N-1$ swaps to put this B after the A (maybe less than that). Then our word can be reduced to WORD_N = [A B WORD_{N-1}].

We se that we have to perform this algorithm as most N-1 times, because the last word (WORD_1) will be already ordered. Performing the algorithm N-1 times we have to make

N_swaps = (N-1)*N/2.

where N is half of the lenght of the initial word.

Lets see why we can apply the same algorithm for WORD_{N-1} also assuming that the first word is A. In this case it matters than the first word should be the same as in the already ordered pair. We can be sure that the first character in WORD_{N-1} is A because it was the character just next to the first character in our initial word, ant if it was B the first work can perform only a swap between these two words and or none and we will already have WORD_{N-1} starting with the same character than WORD_{N}, while the first two characters of WORD_{N} are different at the cost of almost 1 swap.

Answer 4

Observe that if any solution would swap two instances of the same letter, then we can find a better solution by dropping that swap, which necessarily has no effect. An optimal solution therefore only swaps differing letters.

Let's view the string of letters as an array of indices of one kind of letter (arbitrarily chosen, say A) into the string. So AAAABBBB would be represented as [0, 1, 2, 3] while ABABABAB would be [0, 2, 4, 6].

We know two instances of the same letter will never swap in an optimal solution. This lets us always safely identify the first (left-most) instance of A with the first element of our index array, the second instance with the second element, etc. It also tells us our array is always in sorted order at each step of an optimal solution.

Since each step of an optimal solution swaps differing letters, we know our index array evolves at each step only by incrementing or decrementing a single element at a time.

An initial string of length n = 2k will have an array representation A of length k. An optimal solution will transform this array to either

ODDS = [1, 3, 5, ... 2k]

or

EVENS = [0, 2, 4, ... 2k - 1]

Since we know in an optimal solution instances of a letter do not pass each other, we can conclude an optimal solution must spend min(abs(ODDS[0] - A[0]), abs(EVENS[0] - A[0])) swaps to put the first instance in correct position.

By realizing the EVENS or ODDS choice is made only once (not once per letter instance), and summing across the array, we can count the minimum number of needed swaps as

define count_swaps(length, initial, goal)
  total = 0
  for i from 0 to length - 1
    total += abs(goal[i] - initial[i])
  end
  return total
end

define count_minimum_needed_swaps(k, A)
  return min(count_swaps(k, A, EVENS), count_swaps(k, A, ODDS))
end

Notice the number of loop iterations implied by count_minimum_needed_swaps is 2 * k = n; it runs in O(n) time.

By noting which term is smaller in count_minimum_needed_swaps, we can also tell which of the two goal states is optimal.

Answer 5

Since you know N, you can simply write a loop that generates the values with no swaps needed.

#define N 4
char array[N + N];

for (size_t z = 0; z < N + N; z++)
{
    array[z] = 'B' - ((z & 1) == 0);
}

return 0;   // The number of swaps