Implementación recursiva de la suma hasta un objetivo en Python

20 Jul, 2023 Programación 0

Tengo el siguiente método que, dado un entero objetivo, genera todas las formas de crear ese entero a partir de una fila ordenada de enteros, sujeto a la condición de que el índice de columna (comenzando desde uno) multiplicado por el número sume al objetivo para cada fila.

A continuación se muestra un código que logra esto.

target = 7
for x in range(math.floor(target/4)+1):
    for f in range(math.floor((target-4)/3)+1):
        for t in range(math.floor((target-4<em>x-3</em>f)/2)+1):
            s = target - 2<em>t - 3</em>f - 4*x
            print(s,t,f,x)

7 0 0 0
5 1 0 0
3 2 0 0
1 3 0 0
4 0 1 0
2 1 1 0
0 2 1 0
3 0 0 1
1 1 0 1
0 0 1 1

Observa que todas las filas suman a target=7, es decir, toma la última fila 0*1 + 0*2 + 1*3 + 1*4=7.

En el caso general, no sé el número de columnas que necesito. Por ejemplo, simplemente puedo tener:

target = 7
for t in range(math.floor(target/2)+1):
    s = target - 2*t
    print(s,t)

o incluso, muchos más bucles for.

¿Cómo puedo generalizar esto, probablemente basado en una solución recursiva, para que el número de columnas sea un parámetro?

davy.ai

July 20, 2023 at 3:11 am

Para generalizar esta solución para cualquier número de columnas, podemos implementar una función recursiva que tome como parámetros el entero objetivo, el número de columnas y una lista de coeficientes para cada columna.

Aquí tienes un ejemplo de implementación en Python:

def generar_combinaciones(objetivo, num_cols, coeficientes=[]):
    if num_cols == 1:
        coeficientes.append(objetivo)
        print(coeficientes)
    else:
        for x in range(math.floor(objetivo/num_cols)+1):
            nuevos_coeficientes = coeficientes.copy()
            nuevos_coeficientes.append(x)
            generar_combinaciones(objetivo - x*num_cols, num_cols - 1, nuevos_coeficientes)

Esta función utiliza un enfoque recursivo para iterar sobre todas las posibles combinaciones de coeficientes para cada columna, mientras se realiza un seguimiento del entero objetivo restante en cada paso.

El caso base se da cuando se ha alcanzado la última columna (es decir, num_cols == 1), momento en el que simplemente podemos agregar el entero objetivo restante a la lista de coeficientes y imprimir el resultado.

De lo contrario, iteramos sobre todos los posibles valores del coeficiente actual de la columna (x), y llamamos recursivamente a la función con el entero objetivo actualizado (objetivo - x*num_cols) y el número de columnas (num_cols - 1). También creamos una nueva lista de coeficientes (nuevos_coeficientes) en cada iteración, y añadimos el coeficiente actual a esta lista antes de pasarlo a la llamada recursiva.

Para usar esta función, simplemente llámala con el entero objetivo y el número de columnas como parámetros:

objetivo = 7
num_cols = 4
generar_combinaciones(objetivo, num_cols)

Esto generará todas las posibles combinaciones de coeficientes para crear el entero objetivo usando el número especificado de columnas, e imprimirá cada combinación en la consola. Por ejemplo, la salida para objetivo = 7 y num_cols = 4 debería ser:

[0, 0, 0, 7]
[0, 0, 1, 5]
[0, 0, 2, 3]
[0, 1, 0, 4]
[0, 1, 1, 2]
[0, 2, 0, 1]
[1, 0, 0, 3]
[1, 0, 1, 1]
[1, 1, 0, 0]

Ten en cuenta que la salida siempre enumera los coeficientes en orden de índices de columna crecientes (es decir, de izquierda a derecha).

Answer

davy.ai

July 20, 2023 at 3:11 am
Para generalizar esta solución para cualquier número de columnas, podemos implementar una función recursiva que tome como parámetros el entero objetivo, el número de columnas y una lista de coeficientes para cada columna.

Aquí tienes un ejemplo de implementación en Python:
```
def generar_combinaciones(objetivo, num_cols, coeficientes=[]):
    if num_cols == 1:
        coeficientes.append(objetivo)
        print(coeficientes)
    else:
        for x in range(math.floor(objetivo/num_cols)+1):
            nuevos_coeficientes = coeficientes.copy()
            nuevos_coeficientes.append(x)
            generar_combinaciones(objetivo - x*num_cols, num_cols - 1, nuevos_coeficientes)
```
Esta función utiliza un enfoque recursivo para iterar sobre todas las posibles combinaciones de coeficientes para cada columna, mientras se realiza un seguimiento del entero objetivo restante en cada paso.

El caso base se da cuando se ha alcanzado la última columna (es decir, num_cols == 1), momento en el que simplemente podemos agregar el entero objetivo restante a la lista de coeficientes y imprimir el resultado.

De lo contrario, iteramos sobre todos los posibles valores del coeficiente actual de la columna (x), y llamamos recursivamente a la función con el entero objetivo actualizado (objetivo - x*num_cols) y el número de columnas (num_cols - 1). También creamos una nueva lista de coeficientes (nuevos_coeficientes) en cada iteración, y añadimos el coeficiente actual a esta lista antes de pasarlo a la llamada recursiva.

Para usar esta función, simplemente llámala con el entero objetivo y el número de columnas como parámetros:
```
objetivo = 7
num_cols = 4
generar_combinaciones(objetivo, num_cols)
```
Esto generará todas las posibles combinaciones de coeficientes para crear el entero objetivo usando el número especificado de columnas, e imprimirá cada combinación en la consola. Por ejemplo, la salida para objetivo = 7 y num_cols = 4 debería ser:
```
[0, 0, 0, 7]
[0, 0, 1, 5]
[0, 0, 2, 3]
[0, 1, 0, 4]
[0, 1, 1, 2]
[0, 2, 0, 1]
[1, 0, 0, 3]
[1, 0, 1, 1]
[1, 1, 0, 0]
```
Ten en cuenta que la salida siempre enumera los coeficientes en orden de índices de columna crecientes (es decir, de izquierda a derecha).

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Implementación recursiva de la suma hasta un objetivo en Python

Answer

davy.ai