// Extend Array to add permutations. Wanted to // extend Array for all types, but it isn't possible // at the moment. fun Array.permutations(): Array> { // Create a class to remember state information // with the elements that have been processed, // the remaining elements that need processing, // and current position. class State(val processed: Array, val remainder: Array, var position: Int = 0) { // Based on the initial state, generate a new // state each time we are called, until there // aren't anymore. There will be a new state // for each of the remaining elements. fun next(): State? { // Default to done and, if we aren't, allocate // the finished and left arrays, increment the // current position, and return a new state. // Take the current position element out of // the remainder and tack it on to the end of // the processed. var result: State? = null if (position < remainder.size) { val start = Array(processed.size+1, {index -> if (index == processed.size) remainder[position] else processed[index]}) val end = Array(remainder.size-1, {index -> if (index >= position) remainder[index+1] else remainder[index]}) position++ result = State(start, end) } // if return result } // next } // State // Allocate the list of permutation arrays and // stack to remember our state. Push our initial // state on the stack and loop until the stack // becomes empty. val result = mutableListOf>() val stack = mutableListOf() stack.add(State(Array(0, {}), Array(this.size, {index -> this[index]}))) while (!stack.isEmpty()) { // Pop the current state information off the // stack. If this state has a completed // permutation, copy the current sequence // into a new resultant list element. val current = stack.removeAt(stack.size-1) if (current.processed.size == this.size) result.add(Array(this.size, {index -> current.processed[index]})) // Otherwise, generate as many new states for // the stack as possible. else { var next = current.next() while (next != null) { stack.add(next) next = current.next() } // while } // if } // while // Take the mutable list result to create the // return array. return Array(result.size, {index -> result[index]}) } // permutations // Generate the permutations and print them. fun main(args: Array) { // Allocate a mixed type array and generate the // permutations. val array = arrayOf(1, true, "c", 4.0).permutations() // Display the array of permutations by displaying // each element in each permutation using standard // array notations. One permutation per line. for ((position, elements) in array.withIndex()) { if (position == 0) print("[[") else print(" [") for ((index, element) in elements.withIndex()) if (index < elements.size-1) print(element.toString()+", ") else print(element.toString()) if (position < array.size-1) println("],") else println("]]") } // for } // main

permutations mn