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

Question

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

输入为:字符串长度,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/athxu.

在我的设置中,第一个在大约40秒内执行,第二个在4分钟内执行.

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

Answer 1

@ KennyOstrom在那里是90%.反演计数确实是看待这个问题的直角.

唯一缺少的是我们需要一个"相对"反转计数,这意味着反转的数量不是达到正常的排序顺序而是达到另一个单词的顺序.因此,我们需要计算将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_)