Sorting algorithms/Permutation sort: Difference between revisions
Added Kotlin
m (→{{header|REXX}}: added/changed comments and whitespace, changed indentations, aligned more statements.) |
(Added Kotlin) |
||
Line 856:
<lang sh>$ jq -c -n -f Permutation_sort.jq
[true,0,1,"too",{"a":0},{"a":1}]</lang>
=={{header|Kotlin}}==
<lang scala>// version 1.1.1
fun <T : Comparable<T>> isSorted(list: List<T>): Boolean {
val size = list.size
if (size < 2) return true
for (i in 1 until size) {
if (list[i] < list[i - 1]) return false
}
return true
}
fun <T : Comparable<T>> permute(input: List<T>): List<List<T>> {
if (input.size == 1) return listOf(input)
val perms = mutableListOf<List<T>>()
val toInsert = input[0]
for (perm in permute(input.drop(1))) {
for (i in 0..perm.size) {
val newPerm = perm.toMutableList()
newPerm.add(i, toInsert)
perms.add(newPerm)
}
}
return perms
}
fun <T : Comparable<T>> permutationSort(input: List<T>): List<T> {
if (input.size == 1) return input
val toInsert = input[0]
for (perm in permute(input.drop(1))) {
for (i in 0..perm.size) {
val newPerm = perm.toMutableList()
newPerm.add(i, toInsert)
if (isSorted(newPerm)) return newPerm
}
}
return input
}
fun main(args: Array<String>) {
val input = listOf('d', 'b', 'e', 'a', 'f', 'c')
println("Before sorting : $input")
val output = permutationSort(input)
println("After sorting : $output")
println()
val input2 = listOf("first", "second", "third", "fourth", "fifth", "sixth")
println("Before sorting : $input2")
val output2 = permutationSort(input2)
println("After sorting : $output2")
}</lang>
{{out}}
<pre>
Before sorting : [d, b, e, a, f, c]
After sorting : [a, b, c, d, e, f]
Before sorting : [first, second, third, fourth, fifth, sixth]
After sorting : [fifth, first, fourth, second, sixth, third]
</pre>
=={{header|Mathematica}}==
| |||