Finden Sie alle Kombinationen aus einer Liste von zahlen mit einer gegebenen Summe

Habe ich eine Liste von zahlen, z.B.

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

Wie Sie sehen können, zahlen können mehr als einmal erscheinen in dieser Liste.

Ich brauchen, um alle Kombinationen dieser zahlen, dass eine bestimmte Summe, z.B. 10.

Elemente in den Kombinationen dürfen nicht wiederholt werden, aber jedes Element in numbers behandelt werden muss, eindeutig, das bedeutet, dass z.B. die beiden 7 in der Liste repräsentieren verschiedene Elemente mit dem gleichen Wert.

Die Reihenfolge ist unwichtig, so dass [1, 9] und [9, 1] sind die gleiche Kombination.

Gibt es keine Längenbeschränkungen für die Kombinationen, [10] ist genauso gültig, wie [1, 2, 7].

Wie kann ich erstellen Sie eine Liste mit allen Kombinationen, die die genannten Kriterien erfüllen?

In diesem Beispiel wäre es [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

InformationsquelleAutor Byte Commander | 2015-12-29

  1. 15

    Könnten Sie itertools zu Durchlaufen, jede Kombination, jeder möglicher Größe, und filter raus, alles was nicht Summe um 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

    Ergebnis:

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

    Leider ist dies so etwas wie O(2^N) Komplexität, so dass es nicht geeignet für die input-Listen, die größer als, sagen wir, 20 Elemente.

    wenn Sie verwirrt sind, im Verständnis der oben genannten code, hier ist eine einfache version des obigen code for i in range(1,len(a)): for s in itertools.Kombinationen(a,i): wenn die Summe(s)==Summe 1: print(s)

    InformationsquelleAutor Kevin

  2. 8

    Den Lösung @kgoodrick angeboten ist groß, aber ich denke, es ist mehr nützlich als generator:

    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)) Erträge [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].

    erklären Sie die Zeile "Ertrag aus subset_sum(Rest -, Ziel -, Teil - + [n], partial_sum + n)"
    Was wäre die Zeit, die Komplexität dieser code?

    InformationsquelleAutor Martin Valgur

  3. 7

    Diese Frage wurde vorher gefragt, siehe @msalvadores Antwort hier. Ich aktualisierte den python-code zur Ausführung in 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

    InformationsquelleAutor kgoodrick

Schreibe einen Kommentar