Permutations Computer Algorithm (Scala)

Permutations.scala

/**
 * Permutations Computer
 * based on Bogolomyn algorithm
 * Author: Alessio Saltarin
 */


/**
 * Computes all permutations of a sequence of numbers
 * @param permSize size of the sequence - ie.: 7 = (1,2,3,4,5,6,7)
 * @example
 *

        val pComputer = new PermutationComputer(7)
        pComputer.compute()
        println(pComputer.toString)
        println("Found " + pComputer.length + " permutations.")

 *
 */
class PermutationComputer(permSize: Int) {

    protected val size = permSize
    protected var bigbox = List[List[Int]]()

    private var level: Int = -1
    private var count: Int = 1
    private val permNumbers = Array.fill[Int](this.size)(0)

    require(permSize > 0)

    def length: Int = this.count      // Number of permutations found
    def permutations = this.bigbox    // Permutations found (as a List)

    def compute() {

        this.visit(0)
        this.count -= 1

    }

    def visit(k: Int) {

        this.level += 1
        this.permNumbers(k) = this.level
        if (this.level == this.size) {
            val currentList = this.permNumbers.toList
            this.bigbox = currentList :: this.bigbox
            this.count += 1
        }
        else for (j <- 0 until this.size) {
            if (this.permNumbers(j) == 0) visit(j)
        }
        this.level -= 1
        this.permNumbers(k) = 0

    }

    def permutationLine(line: List[Int]): String = {

        val sb = new StringBuilder()
        sb.append('[')
        for (number <- line) {
            sb.append(number)
            sb.append(',')
        }
        sb.deleteCharAt(this.permSize*2)
        sb.append(']')
        sb.append(sys.props("line.separator"))
        sb.result

    }

    override def toString(): String = {

        val sb = new StringBuilder()
        for (pLine <- this.bigbox) {
            sb.append(this.permutationLine(pLine))
        }
        sb.result

    }

}