Tengo un problema de kotlin, ¿puedes encontrar una forma elegante de resolverlo?
tan efectivamente tengo una lista de objetos que quiero ordenar en función de si hay una cadena. Este es el objeto modelo.
data class Sequence( val id: String, val previousSequence: List<String> ) Entonces, la secuencia previousSequence le dice si está o no en una cadena y contiene una identificación de otra secuencia (o puede estar vacía). previousSequence es una lista de cadenas, pero puede suponer que la lista solo contendrá una entrada. (No preguntes, heredo un diseño pobre de otra persona)
Tan efectivamente los datos de prueba a continuación
Sequence("2b", listOf("1a")), Sequence("1a", emptyList()), Sequence("3c", listOf("2b")), Sequence("91z", emptyList()), Sequence("92z", listOf("91z")), Sequence("NO_CHAIN", emptyList())da como resultado una lista de listas de la siguiente manera:
[ [ Sequence(id=1a, previousSequence=[]), Sequence(id=2b, previousSequence=[1a]), Sequence(id=3c, previousSequence=[2b]) ], [ Sequence(id=91z, previousSequence=[]), Sequence(id=92z, previousSequence=[91z]) ] ]El siguiente código funciona... usando recursividad. pero esperaba una solución más elegante. ¿Se te ocurre uno?
data class Sequence( val id: String, val previousSequence: List<String> ) @Test fun `Test chaining of sequence`() { val sequences = listOf( Sequence("2b", listOf("1a")), Sequence("1a", emptyList()), Sequence("3c", listOf("2b")), Sequence("91z", emptyList()), Sequence("92z", listOf("91z")), Sequence("NO_CHAIN", emptyList()) ) val sequenceChains = sequences.filter { it.previousSequence.isNotEmpty() } val baseOfChainList = sequences.filter { base -> base.previousSequence.isEmpty() && sequenceChains.any { it.previousSequence.contains(base.id) } } val listOfChains: MutableList<MutableList<Sequence>> = mutableListOf() baseOfChainList.forEach { val individualList: MutableList<Sequence> = mutableListOf() individualList.add(it) individualList.addAll(recursiveAddSequence(it.id, sequenceChains)) listOfChains.add(individualList) } println(listOfChains) } fun recursiveAddSequence(id: String, sequenceChains: List<Sequence>): List<Sequence> { val individualChain: MutableList<Sequence> = mutableListOf() sequenceChains.forEach { if (it.previousSequence.contains(id)) { individualChain.add(it) individualChain.addAll(recursiveAddSequence(it.id, sequenceChains)) } } return individualChain }Podemos resolver esto con el siguiente código:
val (heads, notHeads) = sequences.partition { it.previousSequence.isEmpty() } val sequencesByPrevious = notHeads.associateBy { it.previousSequence.first() } val result = heads.map { head -> generateSequence(head) { sequencesByPrevious[it.id] }.toList() }Primero, preparamos un mapa de elementos por su elemento anterior. Luego, para cada elemento que es la cabeza (no tiene un elemento anterior), iteramos sobre los siguientes elementos paso a paso.
generateSequence() es una parte complicada. Esta función crea una secuencia de elementos perezosos y sin enlazar (tenga en cuenta que es una "secuencia" diferente a la de su ejemplo). Adquiere elementos posteriores aplicando la lambda proporcionada al elemento anterior y lo hace una y otra vez hasta que se vuelve nulo. Esta única línea es un equivalente de este bucle:
val list = mutableListOf<Sequence>() var curr: Sequence? = head while (curr != null) { list += curr curr = sequencesByPrevious[curr.id] }Si no estamos interesados en elementos que no pertenecen a ninguna cadena (no hacen referencia ni son referenciados por ningún otro elemento), simplemente podemos filtrarlos (gracias @Joffrey):
result.filter { it.size > 1 }Como beneficio adicional: si estoy en lo correcto, su solución tiene al menos una complejidad de tiempo cuadrática. La solución anterior es lineal.