使用Ruby和递归查找所有可能的排列

Question

我一直试图解决一个简单的测验问题,找到使用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类有实例方法排列来做到这一点,但我正在努力解决它的实践.

请注意,当前实现的复杂度为O(N!).反正有进一步提升性能吗？

Answer 1

要了解困难可能是什么,让我们尝试一个更简单的例子:

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

请注意,我们必须.dup在发送之前使用字符串insert,因为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,你是谁的照片？

Answer 2

你可以使用Array#permutation:

def permutation(string)
  string.permutation(string.size).to_a
end

permutation('abc'.chars)
# => [["a", "b", "c"], ["a", "c", "b"], ["b", "a", "c"], ["b", "c", "a"],
#     ["c", "a", "b"], ["c", "b", "a"]]

更新没有使用Array#permutation:

def permutation(string)
  return [''] if string.empty?

  chrs = string.chars
  (0...string.size).flat_map { |i|
    chr, rest = string[i], string[0...i] + string[i+1..-1]
    permutation(rest).map { |sub|
      chr + sub
    }
  }
end

permutation('abc')
# => ["abc", "acb", "bac", "bca", "cab", "cba"]