Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements

Question

I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.

So for example: given a = [0, 2, 1, 2] and b = [1, 2, 0, 2]. The minimum number of swaps to convert a into b is 1, namely swap a[0] and a[2].

I've tried implenting the "Minimum number of swaps required to sort an array" algorithm (from geeksforgeeks), but this returns a higher number of swaps than expected.

Some test cases that failed:

a = [1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2]
b = [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0]
expected: <9> but was <16>

a = [0, 0, 1, 2, 1, 2, 1, 1, 2, 2]
b = [2, 0, 2, 2, 1, 2, 1, 1, 1, 0]
expected: <2> but was <4>

Code:

import java.io.*;
import java.util.*;

class GfG {
    // Function returns the
    // minimum number of swaps
    // required to convert array a to array b
    public static int minSwaps(int[] a, int[] b)
    {
        int len = a.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++)
            map.put(a[i], i);

        // Initialize result
        int ans = 0;
        for (int i = 0; i < len; i++) {
            // If the ith element of array a is already equal to the ith element of array b
            // then we don't need to swap anything, so we can move to the next element
            if (a[i] == b[i])
                continue;

            // If we need to swap the ith element of array a with some other element
            // then we can find that element in array a using the index of the ith element of array b
            // that we stored in the map earlier
            int j = map.get(b[i]);

            // Swap the ith element of array a with the jth element
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            // Update the index of the swapped element in the map
            map.put(a[j], j);

            // Increment the answer
            ans++;
        }
        return ans;
    }
}

// Driver class
class MinSwaps {
    // Driver program to test the above function
    public static void main(String[] args)
    {
        int[] a = { 0, 0, 1, 2, 1, 2, 1, 1, 2, 2 }; // for example
        int[] b = { 2, 0, 2, 2, 1, 2, 1, 1, 1, 0 }; // for example
        GfG g = new GfG();
        System.out.println(g.minSwaps(a, b));
    }
}

Answer 1

Ignore already correct A-values. If you can correct two A-values by swapping them, do so. This leaves you with 3-cycles, all 0→1→2→0 or all 0→2→1→0. Each can be corrected with two swaps.

Python implementation, where I keep count of the different mismatches:

from collections import Counter

def solve(A, B):
  ctr = Counter()
  swaps = 0
  for a, b in zip(A, B):
    if a != b:
      if ctr[b, a]:
        ctr[b, a] -= 1
        swaps += 1
      else:
        ctr[a, b] += 1
  print(swaps + ctr.total() // 3 * 2)

solve([1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2], [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0])
solve([0, 0, 1, 2, 1, 2, 1, 1, 2, 2], [2, 0, 2, 2, 1, 2, 1, 1, 1, 0])

Attempt This Online!