用最小数量的拼接将一个数组转换为另一个数组

Convert one array to another with minimal quantity of splices

本文关键字：数组 一个 转换 另一个 小数 拼接      更新时间：2023-09-26

让我们以这个数组

为例
ar = [6,3,5,1,2]

我想将它转换为另一个数组，我可能只使用两个操作-在特定位置插入项(splice(I,0,item))或从特定位置删除项(splice(I,1))。我在寻找使用最小数量的拼接的解决方案。

第二个重要条件是，我们考虑具有唯一值的数组，我们的数组不包含双精度值。

例如

ar1 = [6,3,10,5,1,2];
ar2 = [6,3,1,2,5];

很明显，如果我们想从ar得到ar1，我们只需要一个拼接- ar.splice(2,0,10)。如果我们想要得到ar2，我们需要做两次拼接:ar.splice(2,1)然后push(5)(第二次等于splice(ar.length,0,5))

顺便说一下，这个任务具有天然的实用价值。让我们想象一下，例如，产品列表和产品过滤器。我们分别改变过滤器的设置和列表的变化。并且每一次变化都伴随着jquery缓慢的滑上滑下动画。这个动画可能会向上滑动并隐藏特定的项目，或者插入并向下滑动一个新的项目。我们的任务是减少这些动画的数量。这意味着我们尽量减少列表的dom操作的数量。

操作的数量正好是编辑距离(如果不允许替换)。查看水平距离

您可以修改算法来计算levelshtein距离，以实际输出所需的操作。

我写的代码希望能解决这个问题。这个代码在某种程度上是基于Levenshtein距离概念。它似乎对这个问题很有用，正如在maniek的回答中提到的那样。为了简单起见，我使用了字符串而不是数组，并使用了Python。
原来的问题似乎很容易简化为由同一组整数组成的两个长度相等的数组的问题。因此，我假设初始字符串和目标字符串具有相同的长度，并且由相同的一组字符组成。
Python代码:

import random
# Create random initial (strin) and target (strout) strings
s = "abcdefghijklmnopqrstuvwxyz"
l = list(s)
random.shuffle(l)
strout = ''.join(l)
random.shuffle(l)
strin = ''.join(l)
# Use it for tests
#strin = "63125798"
#strout = "63512897"
print strin, strout
ins_del = 0
for i in xrange(len(strin)-1, -1, -1):
    if strin[i] != strout[i]:
        if strin[i-1] == strout[i]:
            ii = strout.find(strin[i], 0, i)
            strin = strin[:ii] + strin[i] + strin[ii:i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "1:", strin
        else:
            ii = strin.find(strout[i], 0, i-1)
            strin = strin[:ii] + strin[ii+1:i+1] + strout[i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "2:", strin
print strin, strout
# Check the result
for i in xrange(0, len(strin)):
    if strin[i] != strout[i]:
        print "error in", i, "-th symbol"
print "Insert/Delite operations = ", ins_del

输出示例:

kewlciprdhfmovgyjbtazqusxn qjockmigphbuaztelwvfrsdnxy
2: kewlciprdhfmovgjbtazqusxny
1: kewlciprdhfmovgjbtazqusnxy
2: kewlciprhfmovgjbtazqusdnxy
2: kewlciphfmovgjbtazqursdnxy
2: kewlciphmovgjbtazqufrsdnxy
2: kewlciphmogjbtazquvfrsdnxy
2: kelciphmogjbtazquwvfrsdnxy
2: keciphmogjbtazqulwvfrsdnxy
2: kciphmogjbtazquelwvfrsdnxy
2: kciphmogjbazqutelwvfrsdnxy
2: kciphmogjbaquztelwvfrsdnxy
2: kciphmogjbquaztelwvfrsdnxy
1: qkciphmogjbuaztelwvfrsdnxy
2: qkcipmogjhbuaztelwvfrsdnxy
2: qkcimogjphbuaztelwvfrsdnxy
1: qjkcimogphbuaztelwvfrsdnxy
2: qjkcmoigphbuaztelwvfrsdnxy
1: qjokcmigphbuaztelwvfrsdnxy
1: qjockmigphbuaztelwvfrsdnxy
qjockmigphbuaztelwvfrsdnxy qjockmigphbuaztelwvfrsdnxy
Insert/Delite operations =  19
相关文章：