Instantly share code, notes, and snippets.

# guildenstern70/Permutations.scala Last active Dec 22, 2015

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