算法回溯:如何在不存储状态的情况下进行递归

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')

你会打印出所需的结果.

在最近的一次采访中,我被要求在不使用两个变量的情况下这样做.没有在看到的变量中存储状态.当时我无法全脑思考,但我想问一下如何在不存储状态的情况下进行回溯？

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 当然是"看不见的"变量.