Un algoritmo sencillo para agrupar listas mediante reversiones de sublistas

Fuentes: A simple clustering algorithm for lists

Un programador describe un algoritmo intuitivo para agrupar los elementos de una lista en clústeres del mismo valor, inspirado en una partida con piezas magnéticas infantiles tipo Magna-Tiles. La técnica consiste en tomar el último valor de la lista, localizar la siguiente ocurrencia más cercana hacia la izquierda y revertir la sublista comprendida entre ambos puntos, repitiendo el proceso hasta que cada letra queda agrupada al final del arreglo. El autor lo caracteriza como una estrategia codiciosa, ya que optimiza únicamente la situación inmediata en cada paso, y lo emparenta con el pancake sort, aunque subraya que el suyo busca agrupar, no ordenar, y opera sobre una lista en lugar de una pila.

El artículo incluye la implementación en JavaScript de la función cassidyCluster, capaz de aceptar tanto cadenas como arreglos. La solución emplea dos bucles while anidados que localizan el clúster más a la derecha y la siguiente posición donde aparece el valor objetivo, para invertir después el segmento con una función auxiliar de intercambio. El autor reconoce una complejidad temporal O(n²) y descarta una versión recursiva tras experimentar con ella.

El texto reflexiona además sobre la facilidad con que las personas resuelven el problema de forma física, gracias a la lectura visual inmediata del estado, frente a la dificultad de trasladar ese mismo movimiento a un programa. El autor cierra el artículo con una nota lúdica, admitiendo que el algoritmo es ineficiente pero satisfactorio desde el punto de vista conceptual.