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

Question

情况

首先，您有一个数组/列表 A，然后您想将其转换为给定的预期数组/列表 B。您可以对数组应用的唯一操作是 InsertAt 和 DeleteAt，它们可以在列表中的特定索引处插入和删除元素。

note: Array B is always sorted while Array A may not be.

例如，您有一个数组 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 的公共(public)列表中找到最长的递增子序列。
3. 删除所有不在最长递增子序列中的元素。
4. 比较剩下的和B，然后相应地添加元素。

但是，我正在努力实现它......

变更日志

1. 修复了遗漏元素 7 的拼写错误，现在最少操作是 7。
2. 添加了我的想法部分
3. 有一个详细阐述了 Levenshtein 距离(又名最小编辑距离)的答案，不知何故它消失了..但我发现在阅读 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)

在用这段代码进行了一些测试之后，很明显结果是两个阶段的操作。有一个项目被删除的第一阶段初始列表，除了所有属于目标列表(重复)。然后将丢失的项目添加到列表中，直到目标列表已构建。

暂时的结论是，如果我们找到一个算法来确定最初出现在目标列表中的项目的最长子序列首先列出，以相同的顺序但不一定连续，然后给出最短路径。这是一个新的和可能更简单的问题。这可能就是您上面的意思，但从程序的输出中可以清楚得多。

很明显，这个问题可以归结为 longest increasing subsequence 的问题。