转换一个阵列到另一个接头

问题描述：

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

我想把它转换到另一个阵列，我可能只使用两个操作 - 在指定位置插入项目（拼接（i，0，项目））或从特定位置移除项目（拼接（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）（第二个等于拼接（ar.length，0,5））

由这个任务具有自然的实用价值。我们来想象一下，例如，产品清单和产品过滤器。我们分别更改过滤器的设置和列表更改。而每一个变化跟着美丽慢jQuery的滑动 - 向下滑动动画。此动画可能会滑动并隐藏特定项目或插入并向下滑动新项目。任务是缩小这些动画的数量。这意味着我们试图缩小列表中DOM操作的数量。

它总是可以被1个剪接完成 - 删除整个旧数组，插入新的阵列。你究竟在干什么？ – maniek 2013-03-21 09:55:22

你说得对。我更新了我的问题。我只能使用特定类型的拼接，这意味着每个操作可能只是删除或添加一个项目。 – Kasheftin 2013-03-21 10:15:03

数组是否可以包含重复的数字？ – 2013-03-21 10:36:16

答

我写了希望解决问题的代码。这个代码基于Levenshtein距离概念。这个问题似乎非常有用，正如马尼克的回答中所提到的。
为了简单起见，我使用了字符串而不是数组，并使用了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

答

操作次数正好是编辑距离（如果您禁止替换）。查看levenshtein距离。

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

转换一个阵列到另一个接头

相关推荐