Tengo una lista de números, por ejemplo,

numbers = [1, 2, 3, 7, 7, 9, 10]

Como se puede ver, los números pueden aparecer más de una vez en esta lista.

Necesito para obtener todas las combinaciones de estos números que tienen una determinada suma, por ejemplo,10.

Los elementos en las combinaciones no se puede repetir, pero cada elemento en numbers tiene que ser tratada de forma única, que significa, por ejemplo, los dos 7 en la lista representan diferentes elementos con el mismo valor.

El orden no es importante, por lo que [1, 9] y [9, 1] son la misma combinación.

Hay ninguna restricción de longitud para las combinaciones, [10] es tan válida como [1, 2, 7].

¿Cómo puedo crear una lista de todas las combinaciones de cumplimiento de los criterios arriba?

En este ejemplo, sería [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

4 Comentarios

  1. 16

    Usted podría utilizar itertools para iterar a través de cada combinación de cada tamaño posible, y filtrar todo lo que no suma a las 10:

    import itertools
    numbers = [1, 2, 3, 7, 7, 9, 10]
    result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
    print result

    Resultado:

    [(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]

    Por desgracia esto es algo así como O(2^N) la complejidad, por lo que no es adecuado para la entrada de las listas de más de, digamos, 20 elementos.

    • si usted está confundido en la comprensión en el código anterior, aquí es una simple versión de el código de arriba for i in range(1,len(a)): para s en itertools.combinaciones(a,i): si la suma(s)==sum1: imprimir(s)
  2. 10

    La solución de @kgoodrick ofrecidos es genial, pero creo que es más útil como un generador:

    def subset_sum(numbers, target, partial=[], partial_sum=0):
        if partial_sum == target:
            yield partial
        if partial_sum >= target:
            return
        for i, n in enumerate(numbers):
            remaining = numbers[i + 1:]
            yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

    list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)) rendimientos [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].

    • podría usted explicar la línea de «rendimiento de subset_sum(el restante, de destino, parcial + [n], partial_sum + n)»
    • ¿Cuál sería el tiempo de la complejidad de este código?
  3. 7

    Esta pregunta se ha hecho antes, ver @msalvadores respuesta aquí. He actualizado el código de python dado a ejecutar en python 3:

    def subset_sum(numbers, target, partial=[]):
        s = sum(partial)
    
        # check if the partial sum is equals to target
        if s == target:
            print("sum(%s)=%s" % (partial, target))
        if s >= target:
            return  # if we reach the number why bother to continue
    
        for i in range(len(numbers)):
            n = numbers[i]
            remaining = numbers[i + 1:]
            subset_sum(remaining, target, partial + [n])
    
    
    if __name__ == "__main__":
        subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)
    
        # Outputs:
        # sum([3, 8, 4])=15
        # sum([3, 5, 7])=15
        # sum([8, 7])=15
        # sum([5, 10])=15
  4. 0

    Esto funciona…

    from itertools import combinations
    
    
    def SumTheList(thelist, target):
        arr = []
        p = []    
        if len(thelist) > 0:
            for r in range(0,len(thelist)+1):        
                arr += list(combinations(thelist, r))
    
            for item in arr:        
                if sum(item) == target:
                    p.append(item)
    
        return p

Dejar respuesta

Please enter your comment!
Please enter your name here