用最少的步数变换序列

Question

我的问题是，我应该用什么算法来实现一个函数 translate根据以下Python示例工作：

>>> translate('aa', 'a')
[('S', -1)]
>>> translate('a', 'aa')
[('R', 0, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('abc', bca')
[('R', 0, 'x'), ('R', 1, 'y'), ('R', 2, 'z'),
 ('W', 2, 'x'), ('W', 0, 'y'), ('W', 1, 'z')]
>>> translate('abc', 'cabc')
[('R', 2, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('ab', 'bab')
[('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]
>>> translate('abc', 'bcabc')
[('R', 1, 'x'), ('R', 2, 'y'), ('S', 2), ('W', 0, 'x'), ('W', 1, 'y')]

它是与生成最佳代码有关的问题的推广 在我的编译器里。算法就是我想要的所以 解决方案不一定必须是Python。在“现实”中 变量（'x'、'y'和'z'）是机器寄存器 以及字符串索引堆栈位置。你知道吗

从示例中可以看出，该算法是关于转换 从一个字符序列到另一个字符序列的字符串 步数。但有三种可能 要从中选择的操作：

1. 将字符串向左或向右移动N步。如果是的话 右移，引入的新指数充满了 ?个字符。E、 g('S', 2)——将字符串的两个索引移到 右边。你知道吗
2. 将索引处的字符读入变量。无法执行此操作 如果字符串中有任何?字符，则执行。例如 ('R', 4, 'q')——读取索引4处的字符并将其存储在 变量q。你知道吗
3. 将变量中的字符写入目标字符串的索引中。这个 必须在索引范围内。E、 g('W', 1, 'q')——将字符写入 字符串中索引0处的变量q。你知道吗

下面是实现这些操作的简单Python代码和 从ab到bab的转换示例 手动执行：

def shift(str, n): return str[-n:] if n < 0 else '?'*n + str
def read(str, n): assert not '?' in str; return str[n]
def write(str, n, ch): return str[:n] + ch + str[n:]

S = 'ab'
x = read(S, 1)
S = shift(S, 1)
S = write(S, 0, x)

这一系列步骤将与解决方案相对应 [('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]。你知道吗

我有一种感觉，这个问题和 levenshtein编辑距离，但我搞不懂。你也可以 为我写translate算法？你知道吗

如果这个问题描述不够清楚的话，我会添加更多的例子 但我希望是这样。你知道吗

Answer 1

首先，我想我修复了你的Python代码。下面是一个可以运行一系列步骤并给出结果的类。你的例子在结果中留下了?，我认为这是不应该发生的。你知道吗

这是SequenceRunner

class SequenceRunner:

    def __init__(self):
        self.INSTRUCTIONS = {
            'R': self.read,
            'S': self.shift,
            'W': self.write
            }

    def set(self, S):
        self.S = S[::-1]

    def shift(self, n):
        self.S = self.S[-n:] if n < 0 else  '?'*n + self.S

    def read(self, n, v):
        assert not '?' in self.S; return self.S[n]

    def write(self, n, v):
        v = getattr(self, v)
        self.S = self.S[:n] + v + self.S[n+1:]

    def run(self, program):
        for line in program:
            func = self.INSTRUCTIONS[line[0]]
            args = line[1:]
            result = func(*args)
            if result:
                setattr(self, args[-1], result)

    def get(self):
        return self.S[::-1]

下面是如何使用它

c = SequenceRunner()
program = [('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]
c.set('ab')
c.run(program)
print c.get()

从另一个问题中推断出一个算法所需的步骤数：你能做得更好吗？你知道吗