我一直在尝试解决一个简单的测验问题，以使用 Ruby 和递归找到字符串的所有可能排列。

我有以下 Ruby 代码:

def permutation(string)
  return [string] if string.size < 2

  chr    = string.chars.first
  perms  = permutation(string[1..-1])

  result = []

  for perm in perms
    for i in (0..perm.size)
      result << (perm[0..i] + chr + perm[i..-1])
    end
  end

  return result  
end

每当我尝试使用 puts permutation("abc") 测试代码时，我都会得到以下输出:

cacbc
cbabc
cbcac
cbca
cacb
cbab
cba

从理论上讲，这应该是一个非常简单明了的问题，但我确定我做错了什么。很可能它与循环的范围有关。我知道 Ruby Array 类有实例方法 permutation 来做到这一点，但我正在尝试解决它以进行练习。

请注意，当前实现的复杂度为 O(N!)。无论如何，有没有进一步提高性能？

最佳答案

为了看看有什么困难，让我们用一个更简单的例子来尝试一下:

string = "ab"

您想要的结果是 ["ab", "ba"]。让我们看看你得到了什么:

string.size #=> 2

所以我们什么时候不回来

return [string] if string.size < 2
  #=> return ["ab"] if "ab".size < 2

被执行。

接下来我们计算:

chr = string.chars.first #=> "a"

请注意，进行此计算的更直接方法如下:

chr = string[0]  #=> "a"

或者，更好的是，使用 String#chr ,

chr = string.chr #=> "a"

后者说明了为什么 chr 不是变量名的最佳选择。

下一步

perms = permutation(string[1..-1])
  #=> = permutation("b")

我现在将缩进返回值以强调我们正在第二次调用 permutation。 permuation 的参数是:

  string #=> "b"

现在当我们执行:

  return [string] if string.size < 2
  #=> return ["b"] if "b".size < 2

我们返回 ["b"]，所以(回到对 permutation 的原始调用):

perms = ["b"]

与之前计算的 chr => "a" 一起使用。下一页:

result = []

for perm in perms
  for i in (0..perm.size)
    result << (perm[0..i] + chr + perm[i..-1])
  end
end

由于 perms 仅包含单个元素 "b"，因此两个 for 循环简化为:

for i in (0.."b".size)
  result << ("b"[0..i] + "a" + "b"[i..-1])
end

即:

for i in (0..1)
  result << ("b"[0..i] + "a" + "b"[i..-1])
end

请注意 "b"[0..0]、"b"[0..1] 和 "b"[0..- 1] 都等于 "b"[0]，也就是 "b"，而 "b"[1..-1] #=> ''。因此，当i => 0时，我们执行:

result << ("b"[0..0] + "a" + "b"[0..-1])
  #=> result << ("b" + "a" + "b")
  #=> result << "bab"

当 i => 1 时:

result << ("b"[0..1] + "a" + "b"[1..-1])
  #=> result << ("b" + "a" + "")
  #=> result << "ba"

所以:

result => ["bab" + "ba"]

这显然不是您想要的。

您需要做的是将双 for 循环更改为:

for perm in perms
  result << chr + perm
  for i in (1..perm.size-1)
    result << (perm[0..i-1] + chr + perm[i..-1])
  end
  result << perm + chr
end

使用String#insert 方法可以写得更紧凑:

for perm in perms
  for i in (0..perm.size)
    result << perm.dup.insert(i,chr)
  end
end

你通常会看到这样写:

perms.each_with_object([]) do |perm, result|
  (0..perm.size).each { |i| result << perm.dup.insert(i,chr) }
end

请注意，我们必须在发送insert 之前.dup 字符串，因为insert 会修改字符串。

这样做，你不需要result = []。您也不需要 return result，因为 parms.each_with_object 返回 result 并且如果没有 return 语句，方法返回最后计算的数量。此外，您不需要临时变量 perms(或 ch，如果需要的话)。

综合起来，我们有:

def permutation(string)
  return [string] if string.size < 2
  ch = string[0]
  permutation(string[1..-1]).each_with_object([]) do |perm, result|
    (0..perm.size).each { |i| result << perm.dup.insert(i,ch) }
  end
end

让我们试试看:

permutation("ab")
  #=> ["ab", "ba"]
permutation("abc")
  #=> ["abc", "bac", "bca", "acb", "cab", "cba"]
permutation("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"]

Eki，你是照片中的哪一位？

关于ruby - 使用 Ruby 和递归查找所有可能的排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25224321/