将列表转换为所需数组的最小步骤算法.(仅使用InsertAt和DeleteAt)

Question

情况

首先,你有一个数组/列表A,然后你想将它转换为给定的预期数组/列表B. 您可以应用在阵列的唯一行动是InsertAt和DeleteAt他们在哪里能够插入,并从列表中的某些索引中删除的元素.

注意:阵列B始终排序,而阵列A可能不排序.

例如,你有一个数组A. [1, 4, 3, 6, 7]

而你希望它成为 [2, 3, 4, 5, 6, 6, 7, 8]

一种方法是让A接受以下行动:

    deleteAt(0); // which will delete element 1, arrayA now [4, 3, 6, 7]
    deleteAt(0); // delete element 4 which now at index 0
                 // array A now [3, 6, 7]
    insertAt(0, 2); // Insert value to at index 0 of array A
                    // array A now [2, 3, 6, 7]
    insertAt(2, 4); // array now [2, 3, 4, 6, 7]
    insertAt(3, 5); // array Now [2, 3, 4, 5, 6, 7]
    insertAt(5, 6); // array Now [2, 3, 4, 5, 6, 6, 7]
    insertAt(7, 8); // array Now [2, 3, 4, 5, 6, 6, 7, 8]

在上面的例子中,对数组A进行了7次操作,将其转换为我们想要的数组.

因此,我们如何找到将A转换为B的步骤以及最小步骤？谢谢!

顺便说一句,删除A中所有元素的解决方案然后添加从B到A的所有内容仅适用于A&B没有任何共同点的情况.

我的想法

到目前为止我做了什么:

1. 比较阵列A和阵列B,然后保存删除阵列A中无法在阵列B中找到的所有元素.
2. 从A和B的公共列表中找到增长最长的子序列.
3. 删除不在最长的子序列中的所有元素.
4. 比较剩下的B,然后相应地添加元素.

但是,我正在努力实施......

更改日志

1. 修正了丢失元素的拼写错误7,现在最少的操作是7.
2. 添加MY THOUGHTS部分
3. 有一个答案阐述了Levenshtein距离(AKA最小编辑距离),不知何故它消失了.但是我发现在阅读git/git levenshtein.c文件之后真的很有用,它似乎是一个比我已经拥有的更快的算法.但是,我不确定该算法会给我详细的步骤,或者它只能给出最少数量的步骤.

Answer 1

我有一个 python 程序，似乎可以工作，但它不是很短

__version__ = '0.2.0'

class Impossible(RuntimeError): pass

deleteAt = 'deleteAt'
insertAt = 'insertAt' 
incOffset = 'incOffset'

def remove_all(size):
    return [(deleteAt, i, None) for i in range(size-1, -1, -1)]

def index_not(seq, val):
    for i, x in enumerate(seq):
        if x != val:
            return i
    return len(seq)

def cnt_checked(func):
    """Helper function to check some function's contract"""
    from functools import wraps
    @wraps(func)
    def wrapper(src, dst, maxsteps):
        nsteps, steps = func(src, dst, maxsteps)
        if nsteps > maxsteps:
            raise RuntimeError(('cnt_checked() failed', maxsteps, nsteps))
        return nsteps, steps
    return wrapper

@cnt_checked
def strategy_1(src, dst, maxsteps):
    # get dst's first value from src
    val = dst[0]
    try:
        index = src.index(val)
    except ValueError:
        raise Impossible

    # remove all items in src before val's first occurrence
    left_steps = remove_all(index)
    src = src[index:]
    n = min(index_not(src, val), index_not(dst, val))
    score = len(left_steps)
    assert n > 0
    left_steps.append([incOffset, n, None])
    right_steps = [[incOffset, -n, None]]
    nsteps, steps = rec_find_path(src[n:], dst[n:], maxsteps - score)
    return (score + nsteps, (left_steps + steps + right_steps))

@cnt_checked
def strategy_2(src, dst, maxsteps):
    # do not get dst's first value from src
    val = dst[0]
    left_steps = []
    src = list(src)
    for i in range(len(src)-1, -1, -1):
        if src[i] == val:
            left_steps.append((deleteAt, i, None))
            del src[i]
    n = index_not(dst, val)
    right_steps = [(insertAt, 0, val) for i in range(n)]
    dst = dst[n:]
    score = len(left_steps) + len(right_steps)
    nsteps, steps = rec_find_path(src, dst, maxsteps - score)
    return (score + nsteps, (left_steps + steps + right_steps))

@cnt_checked
def rec_find_path(src, dst, maxsteps):

    if maxsteps <= 0:
        if (maxsteps == 0) and (src == dst):
            return (0, [])
        else:
            raise Impossible

    # if destination is empty, clear source
    if not dst:
        if len(src) > maxsteps:
            raise Impossible
        steps = remove_all(len(src))
        return (len(steps), steps)

    found = False
    try:
        nsteps_1, steps_1 = strategy_1(src, dst, maxsteps)
    except Impossible:
        pass
    else:
        found = True
        maxsteps = nsteps_1 - 1
    try:
        nsteps_2, steps_2 = strategy_2(src, dst, maxsteps)
    except Impossible:
        if found:
            return (nsteps_1, steps_1)
        else:
            raise
    else:
        return (nsteps_2, steps_2)

def find_path(A, B):
    assert B == list(sorted(B))
    maxsteps = len(A) + len(B)
    nsteps, steps = rec_find_path(A, B, maxsteps)
    result = []
    offset = 0
    for a, b, c in steps:
        if a == incOffset:
            offset += b
        else:
            result.append((a, b + offset, c))
    return result

def check(start, target, ops):
    """Helper function to check correctness of solution"""
    L = list(start)
    for a, b, c in ops:
        print(L)
        if a == insertAt:
            L.insert(b, c)
        elif a == deleteAt:
            del L[b]
        else:
            raise RuntimeError(('Unexpected op:', a))
    print(L)
    if L != target:
        raise RuntimeError(('Result check failed, expected', target, 'got:', L))

start = [1, 4, 3, 6, 7]
target = [2, 3, 4, 5, 6, 6, 7, 8]

ops = find_path(start, target)
print(ops)

check(start, target, ops)

经过对这段代码的一些测试，现在很明显结果是一个两阶段操作。第一阶段是从初始列表中删除项目，除了递增的项目序列之外的所有项目都属于目标列表（有重复）。然后将缺失的项目添加到列表中，直到构建目标列表。

临时结论是，如果我们找到一种算法来确定第一个列表中最初存在的目标列表中项目的最长子序列，顺序相同但不一定连续，那么它会给出最短路径。这是一个新的且可能更简单的问题。这可能就是您上面的意思，但从程序的输出中可以清楚地看出。

看起来几乎很明显，这个问题可以简化为最长递增子序列的问题