ruby - 算法回溯 : How to do recursion without storing state

Question

通常在回溯中，我们采用一个接受初始状态的辅助函数，每个递归调用负责自己的计算并将结果传递给下一个递归调用。理论上，我们通过看不见和看见的变量来表示这一点。

例如，在一个字符串的排列中，我们将使用这个程序:

def permute(str)
  return str if str.length < 2 
  permute_helper(str, "")
end 

def permute_helper(unseen, seen)
  #base case
  if unseen.length <= 0
    p seen
    return
  else 
    (0..unseen.length-1).each do |i|
      buffer = unseen 
      buffer = buffer.split('')
      buffer.delete_at(i)
      buffer = buffer.join('')
      permute_helper(buffer, seen+unseen[i])
    end 
  end
end 

permute('abc')

Thie 将打印出所需的结果。

在最近的一次采访中，我被要求在不使用两个变量的情况下做到这一点。没有将状态存储在可见变量中。当时想不通，想请教如何在不存储状态的情况下进行回溯？

Answer 1

字符串 "cd" 的排列是 ["cd", "dc"]。如果我们现在希望获得字符串 "bcd" 的排列，我们只需用三个字符串替换此数组的每个元素，每个字符串在不同的位置具有 "b"。 "cd" 变为 "bcd"、"cbd" 和 "cdb" 和 "dc" 变为 “bdc”、“dbc” 和 “dba”。因此 "bcd" 的排列是

["bcd", "cbd", "cdb", "bdc", "dbc", "dba"]

如果我们现在希望获得 "abcd" 的排列，我们将上述六元素数组的每个元素替换为四个字符串，每个字符串为 "a"在不同的位置。例如，"bcd" 变为 "abcd"、"bacd"、"bcad" 和 “bcda”。递归的结构现在应该很明显了。

def permute(str)
  case str.length
  when 0, 1
    str
  when 2
    [str, str.reverse]
  else
    first = str[0]
    sz = str.size-1
    permute(str[1..-1]).flat_map { |s| (0..sz).map { |i| s.dup.insert(i,first) } }
  end
end

permute('')
  #=> ""
permute('a')
  #=> "a"
permute('ab')
  #=> ["ab", "ba"]
permute('abc')
  #=> ["abc", "bac", "bca", "acb", "cab", "cba"]    
permute('abcd')
  #=> ["abcd", "bacd", "bcad", "bcda", "acbd", "cabd", "cbad", "cbda",
  #    "acdb", "cadb", "cdab", "cdba", "abdc", "badc", "bdac", "bdca",
  #    "adbc", "dabc", "dbac", "dbca", "adcb", "dacb", "dcab", "dcba"]

str 当然是“看不见”的变量。