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

通常在回溯中，我们采用一个helper函数，它接受初始状态，每个递归调用负责自己的计算，并将结果传递给下一个递归调用。理论上，我们通过看不见和看到的变量来表示。
例如，在字符串的置换中，我们将使用以下程序：

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

他们将打印出所需的结果。
在最近的一次采访中，我被要求在不使用两个变量的情况下这样做。不在seen变量中存储状态我当时想不透，但我想问，如何在不存储状态的情况下进行回溯？

最佳答案

字符串"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当然是“不可见”变量。