The below is the Scala Code for finding the permutations of the given digits using the Johnson-Trotter algorithm:-

 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()
        }      
    }
}

But, the resultant two dimensional ArrayBuffer contains (1,2,3) six times for the ArrayBuffer input of (1,2,3) instead of showing all the permutations. I believe that the elements are not being swapped. What am I doing wrong here ? Would really appreciate the help.

CodePudding user response：

Array (same as ArrayBuffer) in scala is mutable. When you do result.append(arr), you're adding the references to the same array to the result. When arr is then modified, the modification can be observed in all elements of the result.

One way to fix your code is to replace all instances of result.append(arr) with result.append(arr.clone()).

That is correct, but not very efficient. Another, slightly more efficient approach would be to use Vector[Int] instead of ArrayBuffer, which is immutable and uses structural sharing to perform more efficient updates.

See also How to update a specific element in Immutable Array using Scala