当我传入一个数组时,为什么我的连接会搞乱？

Question

我写了一个方法来置换一个数组(我发现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 bug,还是我在这里遗漏了什么？

Answer 1

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

尝试改变:

result += [arr]

至:

result += [arr.dup]

然后presto!

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

(顺便说一下,你仍然用这个解决方案用最初的'arr'值进行修改,并且可能应该清理它)