,의, 예를 들어 보자 스플 라이스

Question

의 최소한의 양으로 다른

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

내가 다른 배열로 변환 할이 배열을 하나 개의 배열을 변환하고 난 단지 두 가지 작업을 사용할 수 있습니다 - (특정 위치에 항목을 삽입 splice (i, 0, item)) 또는 특정 위치에서 항목을 제거합니다 (splice (i, 1)). 최소의 스플 라이스 양을 사용하는 솔루션을 찾고 있습니다.

두 번째 중요한 조건은 배열에 고유 한 값이 있다고 생각하고 배열에 double을 포함하지 않는 것입니다. 예를 들어

, 우리는 아칸소에서 AR1 얻으려면, 우리는 단 하나의 스플 라이스 필요가 분명

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

- ar.splice (2,0,10)을. ar2를 얻으려면 ar.splice (2,1)을 누른 다음 push (5) (두 번째는 splice (ar.length, 0,5)와 같습니다)

By 이 작업은 자연스러운 실용적인 가치가 있습니다. 예를 들어, 제품 및 제품 필터 목록을 상상해 봅시다. 필터의 설정을 변경하고 목록이 각각 변경됩니다. 그리고 아름다움 슬로우 jquery 슬라이드에 따라 모든 변화 - 애니메이션 아래로 슬라이드. 이 애니메이션은 특정 항목을 위로 이동하거나 숨기거나 새 항목을 삽입하고 아래로 슬라이드 할 수 있습니다. 임무는 애니메이션의 수량을 줄이는 것입니다. 이는 우리가 목록의 DOM 조작 수를 줄이려고한다는 것을 의미합니다.

Answer 1

문제를 해결하기 위해 코드를 작성했습니다. 이 코드는 어떻게 든 Levenshtein 거리 개념을 기반으로합니다. maniek의 답변에서 언급했듯이이 문제는 매우 유용합니다.
간단히하기 위해 배열 대신 문자열로 작업하고 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 

Answer 2

작업 수는 정확히 편집 거리입니다 (대체를 허용하지 않는 경우). levenshtein 거리를보세요.

알고리즘을 수정하여 수평 거리를 계산하여 필요한 작업을 실제로 출력 할 수 있습니다.