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

我想获得将一个字符串转换为匹配第二个字符串所需的最小字母交换次数。仅允许相邻交换。

输入为：字符串长度、string_1、string_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/8hp46 and https://ufile.io/athxu https://ufile.io/athxu.

在我的设置中，第一个命令在大约 40 秒内执行，第二个命令在 4 分钟内执行。

如何在不到20秒的时间内计算出结果？

@KennyOstrom 的 90% 都在那里。倒数计数确实是看待这个问题的正确角度。

唯一缺少的一点是我们需要一个“相对”反转计数，这意味着反转的数量不是达到正常的排序顺序，而是达到另一个单词的顺序。因此，我们需要计算将 word1 稳定映射到 word2（或相反）的排列，然后计算其反转计数。稳定性在这里很重要，因为显然会有很多非唯一的字母。

这是一个 numpy 实现，对于您发布的两个大型示例，只需一两秒钟。我没有对其进行广泛的测试，但它确实与@trincot 在所有测试用例上的解决方案一致。对于它发现的两个大对1819136406 and 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_)