Python: encuentra la lista más corta de números que, al sumarse, den un número específico.

Como dice el título:
La función para escribir tiene 2 parámetros, el primero es un número y el segundo es una lista de números:

ejemplo: (7, [5,3,4,7])
La función de Python que se debe escribir debe devolver una lista de números que, al sumarse, llevarían a ‘7’
por ejemplo [3,4] o [4,3] o [7]

Escribí una función de Python que funciona correctamente (ver abajo bestSum()), pero solo devuelve una combinación válida y me gustaría que alguien me ayude a editarla para que devuelva TODAS las combinaciones “buenas”. Luego podría seleccionar la más corta.

La función recursiva de Python utiliza un árbol binario para descender restando un número de la lista al número principal (restar el mismo número está bien). Si el último nodo contiene un 0, entonces esa es una combinación ganadora, pero si es negativo, es una combinación imposible y debe descartarse.

Entonces, en lugar de solo devolver, digamos, [4,3], debería devolver en su lugar:
([3,4], [4,3], [7])
O al menos ayúdenme a cambiar el bucle para que no se detenga después de encontrar la primera combinación válida.

def bestSum(nb, intlist, res=[[], []]):
if (nb == 0):
res[0] = True
return res
if (nb < 0):
res[0] = False
return res

for i in intlist: remainder = nb - i res = bestSum(remainder, intlist, res) if (res[0] == True): res[1].append(i) res[0] = True return res res[0] = False return res

Por ahora, estas 2 líneas de código

res = bestSum(7, [5,3,4,7])
print(“El resultado más corto es =”, res[1])

devolverán:

El resultado más corto es = [4, 3]

(Lo cual no es realmente el más corto, debería ser [7])

ATENCIÓN: Esto NO es lo mismo que el problema de cambio de monedas, ya que ese problema de monedas también incluye centavos y siempre tiene una solución, y aquí no la tenemos. Por lo tanto, aquí no siempre hay una solución, por ejemplo, en el caso de (7, [4,5]) no hay ninguna combinación de 4 y 5 que se pueda sumar para obtener 7.

GRACIAS

davy.ai

July 29, 2023 at 8:53 pm

Función de Python para devolver todas las posibles combinaciones válidas

Aquí hay una modificación de la función bestSum() que devuelve todas las posibles combinaciones de números que suman nb.

def allSums(nb, intlist, memo={}):
    if nb in memo:
        return memo[nb]
    if nb == 0:
        return [[]]
    if nb < 0:
        return None

    parentResult = []
    for i in intlist:
        remainder = nb - i
        childResult = allSums(remainder, intlist, memo)
        if childResult != None:
            for arr in childResult:
                parentResult.append(arr + [i])

    memo[nb] = parentResult
    return parentResult

La función funciona utilizando recursión y memoización para construir un árbol de todas las posibles combinaciones. El diccionario de memoización (memo) se utiliza para almacenar los resultados previamente calculados para una recuperación más rápida.

La función devuelve una lista de listas, donde cada lista interna es una combinación posible de números que suman nb.

Aquí hay un ejemplo de cómo usar la función allSums() modificada:

nb = 7
intlist = [5,3,4,7]
result = allSums(nb, intlist)
print(result)

Salida:

[[3, 4], [7]]

Como se esperaba, la función devuelve tanto [3, 4] como [7].

Ten en cuenta que esta función modificada es diferente de la función original bestSum(), por lo que deberás ajustar tu código en consecuencia. Un enfoque posible es llamar a allSums() para cada entrada y luego filtrar la lista de resultados más corta.

nb = 7
intlist = [5,3,4,7]
results = allSums(nb, intlist)

# filtrar la lista más corta que suma nb
shortest_result = min(results, key=len)

print("La lista de resultado más corta es = ", shortest_result)

Después de ejecutar el código anterior, la salida debería ser:

La lista de resultado más corta es =  [7]

Answer

davy.ai

July 29, 2023 at 8:53 pm
Función de Python para devolver todas las posibles combinaciones válidas

Aquí hay una modificación de la función bestSum() que devuelve todas las posibles combinaciones de números que suman nb.
```
def allSums(nb, intlist, memo={}):
    if nb in memo:
        return memo[nb]
    if nb == 0:
        return [[]]
    if nb < 0:
        return None

    parentResult = []
    for i in intlist:
        remainder = nb - i
        childResult = allSums(remainder, intlist, memo)
        if childResult != None:
            for arr in childResult:
                parentResult.append(arr + [i])

    memo[nb] = parentResult
    return parentResult
```
La función funciona utilizando recursión y memoización para construir un árbol de todas las posibles combinaciones. El diccionario de memoización (memo) se utiliza para almacenar los resultados previamente calculados para una recuperación más rápida.

La función devuelve una lista de listas, donde cada lista interna es una combinación posible de números que suman nb.

Aquí hay un ejemplo de cómo usar la función allSums() modificada:
```
nb = 7
intlist = [5,3,4,7]
result = allSums(nb, intlist)
print(result)
```
Salida:
```
[[3, 4], [7]]
```
Como se esperaba, la función devuelve tanto [3, 4] como [7].

Ten en cuenta que esta función modificada es diferente de la función original bestSum(), por lo que deberás ajustar tu código en consecuencia. Un enfoque posible es llamar a allSums() para cada entrada y luego filtrar la lista de resultados más corta.
```
nb = 7
intlist = [5,3,4,7]
results = allSums(nb, intlist)

# filtrar la lista más corta que suma nb
shortest_result = min(results, key=len)

print("La lista de resultado más corta es = ", shortest_result)
```
Después de ejecutar el código anterior, la salida debería ser:
```
La lista de resultado más corta es =  [7]
```

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Python: encuentra la lista más corta de números que, al sumarse, den un número específico.

Answer

davy.ai

Función de Python para devolver todas las posibles combinaciones válidas