将数组1更改为数组2所需的最小交换数?

正如@IVlad在对你的问题的评论中指出的那样 Yodaness problem 让你数数 number of inversions 而不是最小数量的交换。

例如:

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

交换的最小数目是 一 (交换5和3英寸 L2 得到 L1 ),但倒数是 :(5 4)、(5 3)和(4 3)对顺序错误。

计算倒数的最简单方法如下 the definition :

_我 ,第 _{j 我} &燃气轮机;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)) a merge sort algorithm 工作)。下面是来自 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])

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)

输出:

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

正如Sebastian的解决方案所暗示的,您正在寻找的算法可以基于检查 permutation's cycles .

每个排列都可以表示为一组不相交的循环,表示项的循环位置变化。例如置换P有2个循环:(2,1)和(4,3)。因此,两次互换就足够了。在一般情况下,只需从置换长度中减去循环数,即可得到所需交换的最小数目。这是根据观察得出的,为了“固定”一个由N个元素组成的循环,N-1次交换就足够了。

这个问题有一个干净、贪婪、琐碎的解决方案:

1. 找到任何交换操作 二者都
2. 重复步骤1,直到不再存在此类交换操作。
3. 找到任何交换操作 一
4. 返回步骤1,直到Array1==Array2。

这可以很容易地转换成另一种类型的问题,可以更有效地解决。所需要的只是将数组转换为置换,即将值更改为它们的id。因此,您的阵列:

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

会变成

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

2->0, 3->1, 4->2, 5->3

将排列从一个转换到另一个可以转换为类似的问题( Number of swaps in a permutation )通过将O(n)中的目标置换求逆,将O(n)中的置换合成,然后求出从那里到O(m)中的恒等置换的交换数。

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)

为了计算步数,可以设计一个简单的算法,例如:

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;
}

而且很重要 一次交换。现在,假设它返回的交换数确实是最小的,那么算法的运行时就受到它的限制,并且保证完成(而不是陷入无限循环)。它会跑进来的 O(m) 交换或 O(m + n) 循环迭代,其中 m 是交换数量(即 count 返回)和 n 是序列中的项目数( 4 m < n 一切都是真的。因此,这应该优于 O(n log n) 解决方案,因为上限是 O(n - 1) O(n + n - 1) O(n) (后一种情况中省略常数因子2)。

该算法只适用于有效的置换,对于具有重复值的序列将无限循环,对于具有非重复值的序列将执行越界数组访问(和崩溃) [0, n) here (使用visualstudio2008构建,算法本身应该是相当可移植的)。它生成所有可能的长度为1到32的排列,并检查用广度优先搜索(BFS)生成的解决方案,似乎对长度为1到12的所有排列都有效,然后它变得相当慢,但我假设它将继续工作。

算法:

2. 迭代整个列表元素的过程。

代码:

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

因为我们已经知道arr2具有arr1中每个元素的正确索引。因此,我们可以简单地比较arr1元素和arr2元素,并用正确的索引替换它们,以防它们位于错误的索引。

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.塞巴斯蒂安和@Eyal Schneider的回答很酷。 我在解决一个类似的问题时受到启发: 计算排序数组所需的最小交换 ,例如:排序 {2,1,3,0} ,您至少需要2次交换。

// 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;
}

这看起来像是一个 edit distance 问题,除了只允许换位。

Damerau–Levenshtein distance 伪代码。我相信你可以把它调整到只数换位。