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

推荐答案正如@IVlad 在对您的问题的评论中所指出的 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.例如:L1 = [2,3,4,5]L2 = [2,5,4,3]最小交换次数是1(交换L2中的5和3以获得L1)，但反转次数是三:(5 4)、(5 3)和(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:一对元素 (pi,pj) 如果 i i >pj. A pair of elements (pi,pj) is called an inversion in a permutation p if i < j and pi > pj.在 Python 中: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)))您可以使用divide & 计算O(N*log(N)) 中的反转.征服策略(类似于合并排序算法的工作原理).这是来自 Counting Inversions 转换为 Python 代码: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, cdef 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 解决方案: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)输出:number of inversions: 11number of swaps: 5get_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 permutationdef 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 这篇关于将阵列 1 更改为阵列 2 所需的最少交换次数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！