用最快的方法排序字符串以匹配第二个字符串 - 仅允许相邻交换。

Question

我希望能够找到将一个字符串转换成另一个匹配字符串所需的最小字母交换次数。只允许相邻的交换。

输入是：字符串长度、字符串1、字符串2

一些例子：

Length | String 1 | String 2 | Output
-------+----------+----------+-------
   3   | ABC      | BCA      |   2 
   7   | AABCDDD  | DDDBCAA  |  16
   7   | ZZZAAAA  | ZAAZAAZ  |   6

这是我的代码：

def letters(number, word_1, word_2):

    result = 0

    while word_1 != word_2:
        index_of_letter = word_1.find(word_2[0])
        result += index_of_letter
        word_1 = word_1.replace(word_2[0], '', 1)
        word_2 = word_2[1:]

    return result

它给出了正确的结果，但计算时间应保持在20秒以下。这里有两组输入数据（长度为1,000,000个字符的字符串）：https://ufile.io/8hp46和https://ufile.io/athxu。在我的设置中，第一个大约需要40秒执行，而第二个则需要4分钟。如何在不到20秒的时间内计算结果？

- Stoiczkow

---

请您能否再给几个例子？ - Joe Iddon

我在问题帖中添加了两个额外的示例。 我可以上传所有需要测试的数据。 - Stoiczkow

你能否也给出这些问题的预期答案？ - Paul Panzer

标题中的 srting 是否是故意的，也是有用的吗？ - greybeard

Answer 1

@KennyOstrom的解决方案已经接近完成了。计算逆序对确实是解决这个问题的正确角度。

唯一缺少的部分是我们需要一个“相对”逆序对计数，意思是逆序对的数量并不是为了到达正常排序顺序，而是为了到达另一个单词的顺序。因此，我们需要计算将word1稳定映射到word2（或者反过来）的置换，然后计算该置换的逆序对计数。这里稳定性很重要，因为显然会有很多非唯一的字母。

下面是一个numpy实现，对于您发布的两个大例子仅需一两秒钟即可完成。我没有进行大量测试，但它与@trincot的解决方案在所有测试用例上都一致。对于这两个大的例子，它找到了1819136406和480769230766。

import numpy as np

_, word1, word2 = open("lit10b.in").read().split()
word1 = np.frombuffer(word1.encode('utf8')
                      + (((1<<len(word1).bit_length()) - len(word1))*b'Z'),
                      dtype=np.uint8)
word2 = np.frombuffer(word2.encode('utf8')
                      + (((1<<len(word2).bit_length()) - len(word2))*b'Z'),
                      dtype=np.uint8)
n = len(word1)

o1 = np.argsort(word1, kind='mergesort')
o2 = np.argsort(word2, kind='mergesort')
o1inv = np.empty_like(o1)
o1inv[o1] = np.arange(n)

order = o2[o1inv]

sum_ = 0
for i in range(1, len(word1).bit_length()):
    order = np.reshape(order, (-1, 1<<i))
    oo = np.argsort(order, axis = -1, kind='mergesort')
    ioo = np.empty_like(oo)
    ioo[np.arange(order.shape[0])[:, None], oo] = np.arange(1<<i)
    order[...] = order[np.arange(order.shape[0])[:, None], oo]
    hw = 1<<(i-1)
    sum_ += ioo[:, :hw].sum() - order.shape[0] * (hw-1)*hw // 2

print(sum_)

- Paul Panzer

---

这比我的解决方案快！(+1) 不过，当我使用 OP 提到的第一个大输入时，我确实遇到了一个异常：RuntimeWarning: overflow encountered in int_scalars，在 sum += 这一行。当我检查 ioo[:, :hw].sum() 的值时，它是负数...这似乎很奇怪。 - trincot

奇怪。无法重现。无论是在python2.7 / numpy1.8还是在python3.6 / numpy1.13上都不行。也许是平台问题（int64 vs int32）？如果您键入np.int_，会得到什么？ - Paul Panzer

我之前在运行Python3.6.3（32位）/numpy1.13.3。同时，我安装了Python 64位，这解决了问题，因此看起来确实是平台问题。注意：使用32位/64位Python时，np.int_的结果都是<class 'numpy.int32'>。 - trincot

Answer 2

你的算法运行时间为O(n²)：

• find() 调用需要花费O(n)时间
• replace() 调用会创建一个完全新的字符串，需要花费O(n)时间
• 外层循环执行O(n)次

正如其他人所说，这可以通过使用归并排序计算逆序对来解决，但在本答案中，我尝试保持你的算法不变，保留外层循环和result += index_of_letter，但改变了计算index_of_letter的方式。

改进可以按以下方式完成：

• 预处理word_1字符串，并在以字母为键的字典中记录word_1中每个不同字母的第一个位置。将每个字母与其下一个出现的位置相连。我认为最有效的方法是创建一个大小为word_1的列表，在每个索引处存储相同字母的下一个出现位置的索引。这样，您可以为每个不同字母创建一个链表。此预处理可以在O(n)时间内完成，并且您可以用它替换find调用以进行O(1)查找。每次执行此操作时，都会从链表中删除匹配的字母，即字典中的索引移动到下一个出现位置的索引。
• 上述更改将给出绝对索引，而不考虑您算法中删除字母的情况，因此将导致错误结果。为了解决这个问题，可以构建一个二叉树（也是预处理），其中每个节点表示word_1中的一个索引，并给出在给定索引之前（包括自身，如果尚未删除）的实际非删除字母数。二叉树中的节点永远不会被删除（这可能是一种变体解决方案的想法），但计数会调整以反映字符的删除。在这样的删除中，最多需要O(logn)个节点减少值。但除此之外，没有像replace那样重建字符串。这个二叉树可以表示为一个列表，对应于中序遍历序列中的节点。列表中的值将是在该节点之前（包括它自己）的未删除字母的数量。

初始二叉树可以如下所示：

节点中的数字反映其左侧的节点数，包括它们自己。它们存储在numLeft列表中。另一个列表parent预计算父节点所在的索引。

实际代码可能如下：

def letters(word_1, word_2):
    size = len(word_1) # No need to pass size as argument
    # Create a binary tree for word_1, organised as a list
    #   in in-order sequence, and with the values equal to the number of
    #   non-matched letters in the range up to and including the current index:
    treesize = (1<<size.bit_length()) - 1
    numLeft = [(i >> 1 ^ ((i + 1) >> 1)) + 1 for i in range(0, treesize)]
    # Keep track of parents in this tree (could probably be simpler, I welcome comments).
    parent = [(i & ~((i^(i+1)) + 1)) | (((i ^ (i+1))+1) >> 1) for i in range(0, treesize)]
    # Create a linked list for each distinct character
    next = [-1] * size
    head = {}
    for i in range(len(word_1)-1, -1, -1): # go backwards
        c = word_1[i]
        # Add index at front of the linked list for this character
        if c in head:
            next[i] = head[c]
        head[c] = i
    # Main loop counting number of swaps needed for each letter
    result = 0
    for i, c in enumerate(word_2):
        # Extract next occurrence of this letter from linked list
        j = head[c]
        head[c] = next[j]
        # Get number of preceding characters with a binary tree lookup
        p = j
        index_of_letter = 0
        while p < treesize:
            if p >= j:  # On or at right?
                numLeft[p] -= 1  # Register that a letter has been removed at left side
            if p <= j:  # On or at left?
                index_of_letter += numLeft[p] # Add the number of left-side letters
            p = parent[p] # Walk up the tree
        result += index_of_letter
    return result

这个运行时间为 O(nlogn)，其中 logn 的因子由二叉树向上遍历提供。

我对成千上万的随机输入进行了测试，在所有情况下，上述代码产生的结果与您的代码相同。但是...在更大的输入上运行速度要快得多。

- trincot

---

当使用“ABCEDD”和“BCADDE”进行测试时，您的代码给出了2，当我将相同的字符串“ZZZZZZ”附加到两个字符串中时，结果变为3。也许是复制粘贴错误？我不得不将一个“i”更改为“j”才能使其运行。 - Paul Panzer

糟糕，那个任务应该是单独的。已更正。注意：您的解决方案可以更快地得出结果。 - trincot

现在我用你的解决方案和我的解决方案得到了相同的结果。鉴于它是纯Python，你的解决方案非常快。 - Paul Panzer

对我来说完全可以接受。你的解决方案肯定更原创，而我的只是教科书上的东西。让OP的原始方法起作用通常也被认为是一个优点，不依赖非标准库也是如此。所以，我没有任何抱怨。 - Paul Panzer

Answer 3

我假设你只是想快速找到交换次数，而不需要知道具体要交换什么。

搜索如何计算逆序对。通常使用归并排序进行教学。其中一些结果在stackoverflow上，例如使用Python中的合并排序计算拆分逆序对 逆序对是获得排序字符串所需的相邻交换次数。 计算字符串1中的逆序对。 计算字符串2中的逆序对。

---

此处已编辑错误，正确答案请参见更正答案。我通常会删除错误的答案，但是这个答案在正确答案中被引用。

这很有道理，并且它恰好适用于您的所有三个小测试案例，因此我将假设这是您想要的答案。

使用我从免费在线课程中重新学习算法课程时拥有的一些代码（只是为了好玩）：

print (week1.count_inversions('ABC'), week1.count_inversions('BCA'))
print (week1.count_inversions('AABCDDD'), week1.count_inversions('DDDBCAA'))
print (week1.count_inversions('ZZZAAAA'), week1.count_inversions('ZAAZAAZ'))

0 2
4 20
21 15

这与您上面给出的数值相符：2、16 和 6。

- Kenny Ostrom