使用尽可能少的步骤转换序列

Question

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

>>> 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 步数。如果是向右移动，引入的新指数填充了 ?字符。例如('S', 2) -- 将字符串两个索引移动到对。
2. 将索引处的字符读入变量。此操作不能如果字符串中有任何?字符，则执行。例如 ('R', 4, 'q') -- 读取索引 4 处的字符并将其存储在可变q .
3. 将变量中的字符写入目标字符串的索引中。这索引必须在边界内。例如('W', 1, 'q') - 写下字符变量q字符串中的索引 0
。

这是实现这些操作的琐碎 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')] .

我有一种感觉，这个问题之间有一些相似之处 av列文施泰因编辑距离，但我无法弄清楚。你也可以为我编写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()

问题让我更好地理解：您是否需要一种算法来推断从一个字符串到另一个字符串所需的（最少）步骤？