ArrayBuffer 元素不会在 Scala 中交换

Question

以下是使用 Johnson-Trotter 算法查找给定数字排列的 Scala 代码：-

 import scala.collection.mutable.ArrayBuffer

 object Code{

    def factorial(x:Int):Int={
        if(x==0) return 1 else x*factorial(x-1)
    }

    def permutation(arr:ArrayBuffer[Int]):ArrayBuffer[ArrayBuffer[Int]]={
        val len=arr.length;
        var result=new ArrayBuffer[ArrayBuffer[Int]]

        for(i<-Range(0,factorial(len)/len,1)){
            if(i%2==0){
                for(j<-Range(len-1,0,-1)){
                    var c=arr(j)
                    arr(j)=arr(j-1)
                    arr(j-1)=c
                    result.append(arr)
                }
                var c=arr(len-1)
                arr(len-1)=arr(len-2)
                arr(len-2)=c
                result.append(arr)
            }
            else{
                for(j<-Range(0,len-1,1)){
                    var c=arr(j)
                    arr(j)=arr(j+1)
                    arr(j+1)=c
                    result.append(arr)
                }
                var c=arr(0)
                arr(0)=arr(1)
                arr(1)=c
                result.append(arr)
            }
        }
        return result
    }

    def main(args:Array[String]):Unit={
        var arr=ArrayBuffer(1,2,3)
        var perm=permutation(arr)
        for(j<-Range(0,perm.length,1)){
            for(k<-Range(0,perm(0).length,1)){
                println(" "+perm(j)(k))
            }
            println()
        }      
    }
}

但是，对于 (1,2,3) 的 ArrayBuffer 输入，生成的二维 ArrayBuffer 包含 (1,2,3) 六次，而不是显示所有排列。我相信元素没有被交换。我在这里做错了什么？非常感谢您的帮助。

Answer 1

Array（与 ArrayBuffer 相同）在 Scala 中是可变的。当您执行 result.append(arr) 时，您将对同一数组的引用添加到 result。然后修改arr时，可以在result.

的所有元素中观察到修改

修复代码的一种方法是将 result.append(arr) 的所有实例替换为 result.append(arr.clone())。

这是正确的，但效率不高。另一种稍微更有效的方法是使用 Vector[Int] 而不是 ArrayBuffer，它是不可变的并使用结构共享来执行更有效的更新。

另见 How to update a specific element in Immutable Array using Scala

ArrayBuffer 元素不会在 Scala 中交换

ArrayBuffer elements are not being swapped in Scala

swap

scala

permutation