Minimum number of swaps needed to change Array 1 to Array 2?

For example, input is

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

Minimum number of swaps needed are 2.

The swaps need not be with adjacent cells, any two 开发者_运维百科elements can be swapped.

https://www.spoj.com/problems/YODANESS/

---

As @IVlad noted in the comment to your question Yodaness problem asks you to count number of inversions and not minimal number of swaps.

For example:

L1 = [2,3,4,5]
L2 = [2,5,4,3]

The minimal number of swaps is one (swap 5 and 3 in L2 to get L1), but number of inversions is three: (5 4), (5 3), and (4 3) pairs are in the wrong order.

The simplest way to count number of inversions follows from the definition:

A pair of elements (p_i,p_j) is called an inversion in a permutation p if i < j and p_i > p_j.

In Python:

def count_inversions_brute_force(permutation):
    """Count number of inversions in the permutation in O(N**2)."""
    return sum(pi > permutation[j]
               for i, pi in enumerate(permutation)
               for j in xrange(i+1, len(permutation)))

You could count inversion in O(N*log(N)) using divide & conquer strategy (similar to how a merge sort algorithm works). Here's pseudo-code from Counting Inversions translated to Python code:

def merge_and_count(a, b):
    assert a == sorted(a) and b == sorted(b)
    c = []
    count = 0
    i, j = 0, 0
    while i < len(a) and j < len(b):
        c.append(min(b[j], a[i]))
        if b[j] < a[i]:
            count += len(a) - i # number of elements remaining in `a`
            j+=1
        else:
            i+=1
    # now we reached the end of one the lists
    c += a[i:] + b[j:] # append the remainder of the list to C
    return count, c

def sort_and_count(L):
    if len(L) == 1: return 0, L
    n = len(L) // 2 
    a, b = L[:n], L[n:]
    ra, a = sort_and_count(a)
    rb, b = sort_and_count(b)
    r, L = merge_and_count(a, b)
    return ra+rb+r, L

Example:

>>> sort_and_count([5, 4, 2, 3])
(5, [2, 3, 4, 5])

Here's solution in Python for the example from the problem:

yoda_words   = "in the force strong you are".split()
normal_words = "you are strong in the force".split()
perm = get_permutation(normal_words, yoda_words)
print "number of inversions:", sort_and_count(perm)[0]
print "number of swaps:", number_of_swaps(perm)

Output:

number of inversions: 11
number of swaps: 5

Definitions of get_permutation() and number_of_swaps() are:

def get_permutation(L1, L2):
    """Find permutation that converts L1 into L2.

    See http://en.wikipedia.org/wiki/Cycle_representation#Notation
    """
    if sorted(L1) != sorted(L2):
        raise ValueError("L2 must be permutation of L1 (%s, %s)" % (L1,L2))

    permutation = map(dict((v, i) for i, v in enumerate(L1)).get, L2)
    assert [L1[p] for p in permutation] == L2
    return permutation

def number_of_swaps(permutation):
    """Find number of swaps required to convert the permutation into
    identity one.

    """
    # decompose the permutation into disjoint cycles
    nswaps = 0
    seen = set()
    for i in xrange(len(permutation)):
        if i not in seen:           
           j = i # begin new cycle that starts with `i`
           while permutation[j] != i: # (i σ(i) σ(σ(i)) ...)
               j = permutation[j]
               seen.add(j)
               nswaps += 1

    return nswaps

---

As implied by Sebastian's solution, the algorithm you are looking for can be based on inspecting the permutation's cycles.

We should consider array #2 to be a permutation transformation on array #1. In your example, the permutation can be represented as P = [2,1,4,3].

Every permutation can be expressed as a set of disjoint cycles, representing cyclic position changes of the items. The permutation P for example has 2 cycles: (2,1) and (4,3). Therefore two swaps are enough. In the general case, you should simply subtract the number of cycles from the permutation length, and you get the minimum number of required swaps. This follows from the observation that in order to "fix" a cycle of N elements, N-1 swaps are enough.

---

This problem has a clean, greedy, trivial solution:

1. Find any swap operation which gets both swapped elements in Array1 closer to their destination in Array2. Perform the swap operation on Array1 if one exists.
2. Repeat step1 until no more such swap operations exist.
3. Find any swap operation which gets one swapped element in Array1 closer to its destination in Array2. If such an operation exist, perform it on Array1.
4. Go back to step1 until Array1 == Array2.

The correctness of the algorithm can be proved by defining a potential for the problem as the sum of distances of all elements in array1 from their destination in array2.

---

This can be easily converted to another type of problem, which can be solved more efficiently. All that is needed is to convert the arrays into permutations, i.e. change the values to their ids. So your arrays:

L1 = [2,3,4,5]
L2 = [2,5,4,3]

would become

P1 = [0,1,2,3]
P2 = [0,3,2,1]

with the assignment 2->0, 3->1, 4->2, 5->3. This can only be done if there are no repeated items though. If there are, then this becomes harder to solve.

Converting permutation from one to another can be converted to a similar problem (Number of swaps in a permutation) by inverting the target permutation in O(n), composing the permutations in O(n) and then finding the number of swaps from there to an identity permutation in O(m). Given:

int P1[] = {0, 1, 2, 3}; // 2345
int P2[] = {0, 3, 2, 1}; // 2543

// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2                   | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.

int P1_inv[4];
for(int i = 0; i < 4; ++ i)
    P1_inv[P1[i]] = i;
// invert the first permutation in O(n)

int P[4];
for(int i = 0; i < 4; ++ i)
    P[i] = P2[P1_inv[i]];
// chain the permutations in O(n)

int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps in O(num_steps)

To count the steps, a simple algorithm can be devised, such as:

int NumSteps(int *P, int n)
{
    int count = 0;
    for(int i = 0; i < n; ++ i) {
        for(; P[i] != i; ++ count) // could be permuted multiple times
            swap(P[P[i]], P[i]); // look where the number at hand should be
    }
    // count number of permutations

    return count;
}

This always swaps an item for a place where it should be in the identity permutation, therefore at every step it undoes and counts one swap. Now, provided that the number of swaps it returns is indeed minimum, the runtime of the algorithm is bounded by it and is guaranteed to finish (instead of getting stuck in an infinite loop). It will run in O(m) swaps or O(m + n) loop iterations where m is number of swaps (the count returned) and n is number of items in the sequence (4). Note that m < n is always true. Therefore, this should be superior to O(n log n) solutions, as the upper bound is O(n - 1) of swaps or O(n + n - 1) of loop iterations here, which is both practically O(n) (constant factor of 2 omitted in the latter case).

The algorithm will only work for valid permutations, it will loop infinitely for sequences with duplicate values and will do out-of-bounds array access (and crash) for sequences with values other than [0, n). A complete test case can be found here (builds with Visual Studio 2008, the algorithm itself should be fairly portable). It generates all possible permutations of lengths 1 to 32 and checks against solutions, generated with breadth first search (BFS), seems to work for all of permutations of lengths 1 to 12, then it becomes fairly slow but I assume it will just continue working.

---

Algorithm:

1. Check if the elements of list in the same position are equal. If yes, no swap is required. If no, swap the position of list-element wherever the element is matching
2. Iterate the process for the entire list elements.

Code:

def nswaps(l1, l2):
    cnt = 0
    for i in range(len(l1)):
        if l1[i] != l2[i]:
            ind = l2.index(l1[i])
            l2[i], l2[ind] = l2[ind], l2[i]
            cnt += 1
        pass
    return cnt

---

Since we already know that arr2 has the correct indexes of each element present in arr1. Therefore, we can simply compare the arr1 elements with arr2, and swap them with the correct indexes in case they are at wrong index.

def minimum_swaps(arr1, arr2):
    swaps = 0
    for i in range(len(arr1)):
        if arr1[i] != arr2[i]: 
          swaps += 1
          element = arr1[i]
          index = arr1.index(arr2[i]) # find index of correct element
          arr1[index] = element # swap
          arr1[i] = arr2[i]    
    return swaps

---

@J.F. Sebastian and @Eyal Schneider's answer are pretty cool. I got inspired on solving a similar problem: Calculate the minimum swaps needed to sort an array, e.g.: to sort {2,1,3,0}, you need minimum 2 swaps.

Here is the Java Code:

// 0 1 2 3
// 3 2 1 0  (0,3) (1,2)
public static int sortWithSwap(int [] a) {
    Integer[] A = new Integer[a.length];
    for(int i=0; i<a.length; i++)   A[i] = a[i];
    Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class);

    int cycles = 0;
    HashSet<Integer> set = new HashSet<>();
    boolean newCycle = true;
    for(int i=0; i<B.length; ) {
        if(!set.contains(B[i])) {
            if(newCycle) {
                newCycle = false;
                cycles++;
            }
            set.add(B[i]);
            i = B[i];
        }
        else if(set.contains(B[i])) {   // duplicate in existing cycles
            newCycle = true;
            i++;
        }
    }

    // suppose sequence has n cycles, each cycle needs swap len(cycle)-1 times
    // and sum of length of all cycles is length of sequence, so
    // swap = sequence length - cycles
    return a.length - cycles;
}

// a b b c
// c a b b
// 3 0 1 1
private static Object[] mapping(Object[] A) {
    Object[] B = new Object[A.length];
    Object[] ret = new Object[A.length];
    System.arraycopy(A, 0, B, 0, A.length);
    Arrays.sort(A);
    HashMap<Object, Integer> map = new HashMap<>();
    for(int i=0; i<A.length; i++) {
        map.put(A[i], i);
    }

    for(int i=0; i<B.length; i++) {
        ret[i] = map.get(B[i]);
    }
    return ret;
}

---

This seems like an edit distance problem, except that only transpositions are allowed.

Check out Damerau–Levenshtein distance pseudo code. I believe you can adjust it to count only the transpositions.