2

我写了一个排列数组的方法（我意识到 Ruby 带有一个排列函数，但我想练习算法）。我遇到了一个非常奇怪的错误，不知道为什么会这样。

这是我的代码：

def permute(arr)
  permutation(arr.sort)
end

def permutation(arr, result=[])
  k = nil
  result += [arr]
  (arr.length-1).times do |i|
    if arr[i] < arr[i+1]
      k = i
    end
  end
  if k.nil?
    return result
  else
    l = -1
    arr.length.times do |i|
      if arr[k] < arr[i]
        l = i
      end
      l = nil if l == -1
    end
    arr[k], arr[l] = arr[l], arr[k]
    arr = arr[0..k] + arr[k+1..-1].reverse
    return permutation(arr, result)
  end
end

该方法是递归的，并且在每次连续调用时，我都会连接arr到我的result变量，result += [arr]因为我希望该方法返回一个嵌套数组，例如[[1, 2, 3], [1, 3, 2]..]

然而，当我调用这个方法时，它给了我一个完全奇怪的结果。

permute([1,2,3])
=> [[1, 3, 2], [2, 3, 1], [2, 3, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]

为什么最后三个结果都是[3,2,1]？其他数组也不正确。真正奇怪的是，我可以通过将连接更改为result += arr. 通过此更改，我得到以下信息：

permute([1,2,3])
=> [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]

#I know that I can get my desired nested array like so, but that's beside the point
[1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1].each_slice(3).to_a
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

我没有得到我想要的嵌套数组，但输出给了我正确的排列。为什么它现在可以正常工作，但不是我使用的result += [arr]？这是一个 Ruby 错误，还是我在这里遗漏了什么？

4

1 回答 1

5

你被一个常见的红宝石错误所困扰 - 你正在修改原始数组，因为 permutation() 的 'arr' 参数是对数组的引用

尝试改变：

result += [arr]

到：

result += [arr.dup]

然后转眼！

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

（顺便说一句，您仍在使用此解决方案使用原始的“arr”值，并且可能应该清理它）

于 2013-10-11T07:32:41.557 回答