Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Permutations Computer Algorithm (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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment