Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Reusable snippet to get permutations of a list real quick
import kotlin.streams.asStream
fun main(args: Array<String>) {
val listPermutations = ListPermutations(listOf("a", "b", "c", "d"), 2)
listPermutations.forEach { println(it) }
/* [a, b]
[b, a]
[c, a]
[d, a]
[a, c]
[b, c]
[c, b]
[d, b]
[a, d]
[b, d]
[c, d]
[d, c]
*/
val listPermutationsFull = ListPermutations(listOf("a", "b", "c", "d"))
listPermutationsFull.forEach { println(it) }
/*
[a, b, c, d]
[b, a, c, d]
[c, a, b, d]
[d, a, b, c]
[a, c, b, d]
[b, c, a, d]
[c, b, a, d]
[d, b, a, c]
[a, d, b, c]
[b, d, a, c]
[c, d, a, b]
[d, c, a, b]
[a, b, d, c]
[b, a, d, c]
[c, a, d, b]
[d, a, c, b]
[a, c, d, b]
[b, c, d, a]
[c, b, d, a]
[d, b, c, a]
[a, d, c, b]
[b, d, c, a]
[c, d, b, a]
[d, c, b, a]
*/
}
/**
* Represents all permutations of the elements of the given List
*/
class ListPermutations<T>(private val elements: Array<T>, private val elementsPerResult: Int = elements.size) :
kotlin.collections.AbstractCollection<List<T>>() {
constructor(elements: Collection<T>, length: Int = elements.size) : this(
elements.stream().toArray() as Array<T>,
length
)
constructor(
elements: Iterable<T>,
length: Int = elements.count()
) : this(elements.asSequence().asStream().toArray() as Array<T>, length)
val perm get() = Permutations(elements.size, elementsPerResult)
override val size: Int
by lazy { seq.count() }
override fun iterator(): Iterator<List<T>> {
return seq.iterator()
}
val seq get() = perm.iterator().asSequence().map { it.map { inner -> elements[inner] } }
}
// From here on mostly copy'n'pasted from here https://medium.com/@voddan/a-handful-of-kotlin-permutations-7659c555d421
// Credits: https://github.com/voddan @voddan
class Permutations(N: Int, length: Int) : IntCombinations(N) {
init {
if (length > N) {
throw IllegalArgumentException("Length: $length cannot be greater than number of possible elements: $N")
}
}
override val state = mutableListOf<Ring>()
init {
for (i in N downTo 1 + (N - length)) {
state += Ring(i)
}
}
override fun state(): List<Int> {
val items = (0..size - 1).toMutableList()
return state.map { ring -> items.removeAt(ring.state()) }
}
}
interface Circular<T> : Iterable<T> {
fun state(): T
fun inc()
fun isZero(): Boolean // `true` in exactly one state
fun hasNext(): Boolean // `false` if the next state `isZero()`
override fun iterator(): Iterator<T> {
return object : Iterator<T> {
var started = false
override fun next(): T {
if (started) {
inc()
} else {
started = true
}
return state()
}
override fun hasNext() = this@Circular.hasNext()
}
}
}
class Ring(val size: Int) : Circular<Int> {
private var state = 0
override fun state() = state
override fun inc() {
state = (1 + state) % size
}
override fun isZero() = (state == 0)
override fun hasNext() = (state != size - 1)
init {
assert(size > 0)
}
}
abstract class CircularList<E, H : Circular<E>>(val size: Int) : Circular<List<E>> {
protected abstract val state: List<H> // state.size == size
override fun inc() {
state.forEach {
it.inc()
if (!it.isZero()) return
}
}
override fun isZero() = state.all { it.isZero() }
override fun hasNext() = state.any { it.hasNext() }
}
abstract class IntCombinations(size: Int) : CircularList<Int, Ring>(size)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.