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

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 (pi,pj) is called an inversion in a permutation p if i < j and pi > pj.

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

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.


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.

Tags:

Algorithm

Recent Posts