将阵列1更改为阵列2所需的最小交换次数？

Question

例如,输入是

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

需要的最小交换次数是2.

交换不需要与相邻的单元相交,任何两个元素都可以交换.

Answer 1

正如@IVlad在对你的问题的评论中指出的,Yodaness问题要求你计算倒数的数量而不是最小的掉期数.

例如:

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

交换的最小数量是1(交换5和3 L2以获得L1),但是反转的数量是3:(5 4),(5 3)和(4 3)对的顺序错误.

计算倒数的最简单方法来自定义:

如果i <j且p _i > p _j,则在置换p中将一对元素(p _i,p _j)称为反转.

在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)))

您可以O(N*log(N))使用分而治之策略计算反转(类似于合并排序算法的工作方式).这里将Counting Inversions中的伪代码转换为Python代码:

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

例:

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

这是Python中的解决方案,用于解决问题的示例:

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)

输出:

number of inversions: 11
number of swaps: 5

的定义get_permutation()和number_of_swaps()主要有:

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

Answer 2

正如Sebastian的解决方案所暗示的那样,您正在寻找的算法可以基于检查排列的周期.

我们应该将数组#2视为数组#1上的置换变换.在您的示例中,置换可以表示为P = [2,1,4,3].

每个排列可以表示为一组不相交的循环,表示项目的循环位置变化.排列P例如具有2个循环:(2,1)和(4,3).因此,两次交换就足够了.在一般情况下,您应该简单地从排列长度中减去周期数,并获得所需交换的最小数量.这是因为观察到为了"固定"N个元素的循环,N-1交换就足够了.