eine Funktion, die Anzahl der Summen einer bestimmten Zahl zurückgibt.py

Question

Ich muss eine Funktion schreiben, die die Anzahl der Möglichkeiten zum Erreichen einer bestimmten Anzahl durch Hinzufügen von Nummern einer Liste zurückgibt. Zum Beispiel:

print(p([3,5,8,9,11,12,20], 20)) 
should return:5 

Der Code, den ich geschrieben habe, ist:

def pow(lis): 
    power = [[]] 
    for lst in lis: 
     for po in power: 
      power = power + [list(po)+[lst]] 
    return power 

def p(lst, n): 
    counter1 = 0 
    counter2 = 0 
    power_list = pow(lst) 
    print(power_list) 
    for p in power_list: 
     for j in p: 
      counter1 += j 
     if counter1 == n: 
      counter2 += 1 
      counter1 == 0 
     else: 
      counter1 == 0 
    return counter2 

pow() ist eine Funktion, die alle von den Untergruppen der Liste und p gibt sollte die Anzahl der Möglichkeiten gibt die Anzahl n zu erreichen. Ich bekomme immer eine Ausgabe von Null und ich verstehe nicht warum. Ich würde gerne Ihre Eingabe dafür hören. Vielen Dank im Voraus.

Answer 1

Eine One-Pass-Lösung mit einem Zähler, die Zusätze minimieren.

def one_pass_sum(L,target): 
    sums = [0] 
    cnt = 0 
    for x in L: 
     for y in sums[:]: 
      z = x+y 
      if z <= target : 
       sums.append(z) 
       if z == target : cnt += 1 
    return cnt 

diese Weise, wenn n=len(L), machen Sie weniger als 2^n Ergänzungen gegen n/2 * 2^n durch alle Summen berechnen.

EDIT:

Eine effizientere Lösung, zählt, dass nur Wege. Die Idee ist zu sehen, dass, wenn es k Möglichkeiten gibt, z-x zu machen, gibt es k mehr Weg, z zu tun, wenn x entstehen.

def enhanced_sum_with_lists(L,target): 
    cnt=[1]+[0]*target # 1 way to make 0 
    for x in L: 
     for z in range(target,x-1,-1): # [target, ..., x+1, x] 
      cnt[z] += cnt[z-x] 
    return cnt[target] 

Aber Reihenfolge ist wichtig: z muss Nachkomme hier in Betracht gezogen werden, die guten Zählungen (Dank PM 2Ring) zu haben.

Dies kann sehr schnell sein (n*target Ergänzungen) für große Listen.

Zum Beispiel:

>>> enhanced_sum_with_lists(range(1,100),2500) 
875274644371694133420180815 

wird in 61 ms erhalten. Es wird das Zeitalter des Universums brauchen, um es mit der ersten Methode zu berechnen.

Answer 2

Es gibt zwei Tippfehler in Ihrem Code: counter1 == 0 ist ein Boolean, es setzt nichts zurück.

sollte diese Version arbeiten:

def p(lst, n): 
    counter2 = 0 
    power_list = pow(lst)  
    for p in power_list: 
     counter1 = 0 #reset the counter for every new subset 
     for j in p: 
      counter1 += j 
     if counter1 == n: 
      counter2 += 1 
    return counter2 

Answer 3

from itertools import chain, combinations 

def powerset_generator(i): 
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)): 
     yield set(subset) 

def count_sum(s, cnt): 
    return sum(1 for i in powerset_generator(s) if sum(k for k in i) == cnt) 

print(count_sum(set([3,5,8,9,11,12,20]), 20)) 

Answer 4

Als tobias_k und Faibbus erwähnt, haben Sie einen Tippfehler: counter1 == 0 statt counter1 = 0, an zwei Stellen. Der counter1 == 0 erzeugt ein boolesches Objekt von True oder False, aber da Sie das Ergebnis dieses Ausdrucks nicht zuweisen, wird das Ergebnis verworfen. Es wird kein SyntaxError ausgelöst, da ein Ausdruck, der nicht zugewiesen wird, legales Python ist.

Wie John Coleman und B. M. erwähnen, ist es nicht effizient, das volle Powerset zu erstellen und dann jede Teilmenge zu testen, um zu sehen, ob sie die richtige Summe hat. Dieser Ansatz ist in Ordnung, wenn die Eingabesequenz klein ist, aber selbst für Sequenzen mittlerer Größe sehr langsam. Wenn Sie tatsächlich eine Liste erstellen, die die Subsets enthält, anstatt einen Generator zu verwenden und die Subsets zu testen, werden sie bald ausgeführt aus dem RAM.

B. M.Die erste Lösung ist ziemlich effizient, da sie keine Teilmengen erzeugt, die größer als die Zielsumme sind. (Ich bin mir nicht sicher, was B. M. mit dieser diktierten Lösung macht ...).

Aber wir können diesen Ansatz verbessern, indem wir die Liste der Summen sortieren. Auf diese Weise können wir aus der inneren for Schleife ausbrechen, sobald wir eine zu hohe Summe entdecken. Richtig, wir müssen die -Liste auf jeder Iteration der äußeren for-Schleife sortieren, aber glücklicherweise ist Pythons TimSort sehr effizient und für die Sortierung einer Liste mit sortierten Untersequenzen optimiert. Daher ist es ideal für diese Anwendung.

def subset_sums(seq, goal): 
    sums = [0] 
    for x in seq: 
     subgoal = goal - x 
     temp = [] 
     for y in sums: 
      if y > subgoal: 
       break 
      temp.append(y + x) 
     sums.extend(temp) 
     sums.sort() 
    return sum(1 for y in sums if y == goal) 

# test 

lst = [3, 5, 8, 9, 11, 12, 20] 
total = 20 
print(subset_sums(lst, total)) 

lst = range(1, 41) 
total = 70 
print(subset_sums(lst, total)) 

Ausgang

5 
28188 

Mit lst = range(1, 41) und total = 70, dieser Code ist etwa 3 mal schneller als die B. M. listet Version auf.