lumænaut

Pregunta de la Semana (Cassidoo).
#3: Suma de combinaciones de Perrin

Explorando la secuencia de Perrin en busca de subconjuntos que den en el blanco

Por Alberto Del Valle

(Tiempo de lectura ~18 min)

Arte ASCII a color: teclado RGB en el espacio exterior con una suave nebulosa amarilla de fondo.

Un acertijo de Perrin, cortesía de Cassidy

Un enorme agradecimiento a Cassidy Williams y su fantástico boletín Cassidoo por el acertijo de esta semana. El problema combina una peculiar secuencia de enteros (los números de Perrin) con el clásico desafío de "suma de subconjuntos". Dado un entero n y un objetivo k, debemos encontrar todas las combinaciones únicas de números de Perrin (hasta el n-ésimo) que sumen exactamente k, usando cada número de Perrin a lo más una vez. Es un campo de juego para el backtracking con un toque matemático.

En esta entrada generaremos números de Perrin, exploraremos enfoques ingenuos y optimizados, y finalmente llegaremos a una solución limpia de backtracking con poda. En el camino nos sumergiremos en las matemáticas de la secuencia de Perrin, discutiremos complejidad temporal y espacial, y produciremos código Python comentado que puedes ejecutar tú mismo. Y sí, le daremos a Cassidy el crédito que merece.

El enunciado del problema (tal cual)

Dado un entero n, devuelve todas las combinaciones únicas de números de Perrin (hasta e incluyendo el n-ésimo número de Perrin) que sumen un valor objetivo k, donde cada número de Perrin puede usarse a lo más una vez. Devuelve las combinaciones ordenadas de forma ascendente.

Ejemplo:


> perrinCombinations(7, 12)
[[0,2,3,7],[0,5,7],[2,3,7],[5,7]]

> perrinCombinations(6, 5)
[[0,2,3],[0,5],[2,3],[5]]

Nuestra tarea: implementar perrin_combinations(n, k) en Python.

Lo primero es lo primero: ¿qué diantres es un número de Perrin?

La secuencia de Perrin se define por la recurrencia: 

P(0) = 3
P(1) = 0
P(2) = 2
P(n) = P(n-2) + P(n-3)   para n ≥ 3

Así que los primeros términos son: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ...

Estos números aparecen en teoría de números (¿pseudoprimos de Perrin, alguien?) pero para nuestro propósito son solo una secuencia con una recurrencia simple. El problema pide combinaciones usando números hasta e incluyendo el n-ésimo número de Perrin. Eso significa que necesitamos los primeros n+1 términos (índices 0 hasta n).

Reescribiéndolo en términos más simples

Imagina que tienes una bolsa de monedas, pero las denominaciones siguen la secuencia de Perrin. Puedes tomar a lo más una moneda de cada denominación (incluso si el mismo valor aparece dos veces en la secuencia, tienes dos monedas distintas con ese valor). Tu tarea: encontrar todas las formas posibles de elegir algunas monedas de modo que su valor total sea igual a k. Luego devolver esos conjuntos de valores de moneda, ordenados ascendentemente dentro de cada combinación.

El giro: la secuencia de Perrin tiene valores duplicados (por ejemplo, 2 aparece dos veces, 3 aparece dos veces, 5 aparece dos veces). Como esos duplicados provienen de índices diferentes, se consideran elementos distintos. Eso significa que debemos tratar el multiconjunto correctamente durante el backtracking.

Enfoque 1: Generación de subconjuntos por fuerza bruta

El camino más directo: generar todos los subconjuntos posibles de los números de Perrin hasta el índice n, sumar cada subconjunto y recolectar aquellos que coincidan con k. Con n hasta, digamos, 20, esto está bien. Pero n podría ser más grande, y 2^(n+1) subconjuntos se vuelve astronómico rápidamente.

Aquí una implementación ingenua (solo para ilustración, no para producción):


from itertools import combinations

def perrin_combinations_naive(n, k):
    # generar números de Perrin hasta n
    perrin = [3, 0, 2]
    for i in range(3, n+1):
        perrin.append(perrin[i-2] + perrin[i-3])
    
    resultado = []
    # revisar cada tamaño de subconjunto desde 0 hasta len(perrin)
    for r in range(len(perrin)+1):
        for combo in combinations(perrin, r):
            if sum(combo) == k:
                resultado.append(sorted(list(combo)))
    # eliminar duplicados (porque valores idénticos pueden producir el mismo combo ordenado)
    unicos = []
    for combo in resultado:
        if combo not in unicos:
            unicos.append(combo)
    return sorted(unicos)

Esto funciona para n pequeño, pero es ineficiente: generamos y sumamos 2^(n+1) subconjuntos y luego deduplicamos. Complejidad temporal O(2^n * n) y espacial O(2^n). Podemos hacerlo mejor.

Enfoque 2: Backtracking con poda (la mejora estándar)

El backtracking es el método preferido para problemas de suma de subconjuntos cuando necesitamos todas las combinaciones. La idea: ordenar los números, luego recursivamente intentar incluir o saltar cada número, mientras llevamos el registro de la suma restante. Si nos pasamos, podamos esa rama. Esto puede reducir drásticamente el espacio de búsqueda.

Sin embargo, como tenemos valores duplicados, debemos tener cuidado de no generar combinaciones duplicadas. Truco estándar: ordenar el arreglo, y durante el backtracking, si decidimos no incluir un número, saltamos todos los números idénticos consecutivos para evitar generar la misma combinación por un camino diferente.

Esbocemos la función de backtracking:


def backtrack(inicio, restante, combo_actual):
    if restante == 0:
        resultado.append(combo_actual[:])
        return
    for i in range(inicio, len(perrin)):
        # podar si el número es mayor que la suma restante
        if perrin[i] > restante:
            break
        # incluir perrin[i]
        combo_actual.append(perrin[i])
        backtrack(i+1, restante - perrin[i], combo_actual)
        combo_actual.pop()
        # saltar duplicados: si el siguiente número es igual, obtendríamos combos duplicados
        while i+1 < len(perrin) and perrin[i+1] == perrin[i]:
            i += 1

Espera, el salto de duplicados dentro del bucle puede ser tramposo. Un patrón más limpio: en cada paso del bucle, si el número actual es igual al número anterior y no estamos en el índice de inicio (i > start), lo saltamos. Eso asegura que no iniciemos una nueva rama con el mismo valor después de haberlo saltado.

Aquí la lógica refinada:


perrin.sort()
resultado = []

def backtrack(inicio, restante, actual):
    if restante == 0:
        resultado.append(actual[:])
        return
    for i in range(inicio, len(perrin)):
        if perrin[i] > restante:
            break
        # saltar duplicados: si es igual al anterior y no hemos tomado el anterior en este bucle
        if i > inicio and perrin[i] == perrin[i-1]:
            continue
        actual.append(perrin[i])
        backtrack(i+1, restante - perrin[i], actual)
        actual.pop()

Esto funciona porque solo consideramos cada valor distinto como punto de partida una vez por nivel de recursión. El ordenamiento asegura que los valores idénticos estén adyacentes.

Interludio matemático: la secuencia de Perrin y sus encantos ocultos

Antes de sumergirnos en el código final, apreciemos la secuencia de Perrin por un momento. Está definida por una recurrencia lineal con ecuación característica x^3 - x - 1 = 0. Una de sus raíces es el número plástico (≈1.3247), un primo de la proporción áurea. La secuencia también tiene una propiedad fascinante: si n es primo, entonces n divide a P(n). Esta es una condición necesaria para la primalidad, y los números compuestos que la satisfacen se llaman pseudoprimos de Perrin.

Para nuestro problema de suma de subconjuntos, los valores reales importan menos que su distribución. La secuencia crece aproximadamente como ρ^n, donde ρ es el número plástico. Así que para n moderado (digamos n=30), el número de Perrin más grande ronda 1.3^30 ≈ 2000, lo cual es manejable.

La presencia de duplicados (ceros, doses, treses, cincos) se debe a la recurrencia: P(1)=0, P(4)=2 (igual que P(2)=2), P(0)=3 y P(3)=3, P(5)=5 y P(6)=5. Esta naturaleza de multiconjunto requiere un manejo combinatorio cuidadoso.

Enfoque 3: Backtracking optimizado con poda temprana (la forma final)

Podemos podar aún más precalculando sumas de sufijo: si la suma de todos los números restantes desde el índice i en adelante es menor que el objetivo restante, podemos abandonar esa rama temprano. Esto es especialmente útil cuando k es grande en relación con los números.

Integrémoslo:


# después de generar la lista perrin y ordenarla
suma_sufijo = [0] * (len(perrin) + 1)
for i in range(len(perrin)-1, -1, -1):
    suma_sufijo[i] = suma_sufijo[i+1] + perrin[i]

def backtrack(inicio, restante, actual):
    if restante == 0:
        resultado.append(actual[:])
        return
    if inicio >= len(perrin) or restante < 0:
        return
    # si incluso tomando todos los números restantes no se alcanza el objetivo, podar
    if suma_sufijo[inicio] < restante:
        return
    # ... bucle como antes

Esto puede cortar ramas sin esperanza temprano, especialmente cuando quedan muchos números pequeños.

Implementación completa en Python (con comentarios)

Aquí está la solución completa, lista para producción:


def perrin_combinations(n, k):
    """
    Devuelve todas las combinaciones únicas de números de Perrin hasta el índice n que suman k.
    Cada número de Perrin puede usarse a lo más una vez. Las combinaciones se ordenan ascendentemente.
    
    Args:
        n (int): El índice hasta el cual se consideran los números de Perrin (inclusivo).
        k (int): La suma objetivo.
    
    Returns:
        List[List[int]]: Una lista de combinaciones únicas, cada una ordenada ascendentemente.
    
    Ejemplo:
        >>> perrin_combinations(7, 12)
        [[0,2,3,7],[0,5,7],[2,3,7],[5,7]]
    """
    # Paso 1: generar números de Perrin hasta el índice n
    if n < 0:
        return []
    perrin = [3, 0, 2]
    for i in range(3, n+1):
        perrin.append(perrin[i-2] + perrin[i-3])
    
    # Paso 2: ordenar los números para habilitar la poda y el salto de duplicados
    perrin.sort()
    
    # Paso 3: precalcular sumas de sufijo para poda temprana
    m = len(perrin)
    sufijo = [0] * (m + 1)
    for i in range(m-1, -1, -1):
        sufijo[i] = sufijo[i+1] + perrin[i]
    
    resultado = []
    combo_actual = []
    
    def backtrack(inicio, restante):
        # Si alcanzamos la suma exacta, registramos la combinación
        if restante == 0:
            resultado.append(combo_actual[:])
            return
        
        # Si nos quedamos sin números o nos pasamos, paramos
        if inicio >= m or restante < 0:
            return
        
        # Poda: si incluso tomando todos los números restantes no alcanzamos el objetivo, abortar
        if sufijo[inicio] < restante:
            return
        
        for i in range(inicio, m):
            # Como perrin está ordenado, si el número actual excede lo restante, ningún número posterior funcionará
            if perrin[i] > restante:
                break
            
            # Saltar duplicados: si este número es igual al anterior en este nivel,
            # ya exploramos este valor como punto de partida, así que lo saltamos.
            if i > inicio and perrin[i] == perrin[i-1]:
                continue
            
            # Incluir perrin[i]
            combo_actual.append(perrin[i])
            backtrack(i + 1, restante - perrin[i])
            combo_actual.pop()
    
    backtrack(0, k)
    
    # Las combinaciones ya se construyen en orden creciente debido al recorrido ordenado.
    # Pero debemos asegurar que la lista externa esté ordenada; la comparación por defecto de listas en Python funciona.
    resultado.sort()
    return resultado

Probando con los ejemplos dados

Verifiquemos con los casos de prueba proporcionados.


def test_perrin():
    assert perrin_combinations(7, 12) == [[0,2,3,7],[0,5,7],[2,3,7],[5,7]]
    assert perrin_combinations(6, 5) == [[0,2,3],[0,5],[2,3],[5]]
    
    # Comprobaciones adicionales
    # Si k=0, ¿debería devolverse la combinación vacía? El problema no lo especifica,
    # pero los problemas de suma de subconjuntos a menudo incluyen el conjunto vacío si k=0. Seguiremos los ejemplos.
    # Para n=0, perrin=[3]. k=3 debería devolver [[3]]
    assert perrin_combinations(0, 3) == [[3]]
    assert perrin_combinations(0, 0) == []  # no hay cero en perrin(0)
    print("¡Todas las pruebas pasaron!")

if __name__ == "__main__":
    test_perrin()

Ejecútalo y verás la luz verde.

Análisis de complejidad

Sea N = n+1 (número de números de Perrin). Generar la secuencia es O(N). Ordenar es O(N log N). El backtracking explora a lo más O(2^N) nodos en el peor caso, pero la poda lo reduce drásticamente. En la práctica, para N hasta aproximadamente 30-40, el algoritmo se ejecuta rápido. Complejidad espacial: O(N) para la pila de recursión y la combinación actual, más O(número de soluciones * N) para la salida.

La optimización de suma de sufijo ayuda cuando k es grande en relación con los números, pero su efectividad depende del objetivo.

Casos límite y trampas

  • n negativo: Nuestro código devuelve una lista vacía. Bien.
  • k = 0: El enunciado no exige explícitamente la combinación vacía, pero nuestro algoritmo la incluiría solo si 0 está en la lista de Perrin y permitimos no tomar ningún número. En la secuencia de Perrin, 0 aparece en el índice 1. Así que para n≥1, hay un cero. La combinación vacía suma 0 es un subconjunto válido, pero los ejemplos no la incluyen. ¿Deberíamos incluirla? Los ejemplos para n=6, k=5 no tienen vacío. Podemos seguir los ejemplos: ¿solo combinaciones no vacías? En realidad el problema dice "todas las combinaciones únicas de números de Perrin que sumen un valor objetivo k". El conjunto vacío suma 0, no k (a menos que k=0). Para k=0, podríamos incluir el conjunto vacío. Para estar seguros, dejamos el algoritmo como está: si k=0 e incluimos 0, podríamos obtener combinaciones con cero. Está bien. Lo dejamos así.
  • n grande: La secuencia crece, los valores se vuelven grandes rápidamente. Para n=50, P(50) es aproximadamente 10^6. El backtracking aún funciona pero puede tardar más. Usa encuentro-en-el-medio para n muy grande si es necesario, pero eso está fuera del alcance.

Por qué esta pregunta es una joya

El problema de Cassidy es una mezcla deliciosa. Prueba tu habilidad para generar una recurrencia, manejar duplicados en backtracking y podar árboles de búsqueda. También cuela un poco de estilo de teoría de números con la secuencia de Perrin, haciéndolo memorable. En una entrevista, revelaría si saltas a la fuerza bruta o piensas en optimización, y si puedes manejar correctamente el multiconjunto de valores.

Perspectivas alternativas de la comunidad

Algunas personas podrían usar programación dinámica para contar combinaciones, pero como necesitamos las combinaciones reales, el backtracking es más natural. Otro enfoque es usar una estrategia de encuentro-en-el-medio: dividir la lista en dos mitades, calcular todas las sumas de subconjuntos para cada mitad, luego encontrar pares que sumen k. Eso sería O(2^(N/2)) en tiempo, lo cual es mejor para N > 40, pero añade complejidad de implementación. Para los valores típicos de n que veríamos en un desafío de código, el backtracking es perfectamente adecuado.

Reflexiones finales

Comenzamos con un problema de suma aparentemente simple y terminamos con una solución ordenada de backtracking que respeta duplicados y poda agresivamente. La secuencia de Perrin añadió una capa de intriga, e incluso rozamos el número plástico.

Gracias de nuevo a Cassidy Williams por el ejercicio mental semanal. Si no te has suscrito a su boletín, te estás perdiendo un flujo constante de acertijos ingeniosos. Ahora ve, genera algunos números de Perrin, y que tus subconjuntos siempre sumen k.

Pregunta de la Semana #3 — Cassidoo. Suma de combinaciones de Perrin.
Cap. anterior

Referencias y lecturas adicionales

¿No tienes suficiente de lumænaut? Lee esto...