用最少的步驟可能變換順序

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') - 在字符串中的索引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() 

問題讓我更好地瞭解：你需要一個算法，可以推斷出（最低金額）的步驟需要從一個字符串到另一個字符？