Wie kann Python angehalten werden, sobald das Zielprodukt in der Teilmenge gefunden wurde?

Ich habe Python für mein Hobby und meine empirische Forschung zu NP-vollständigen Problemen wie Subset Product gelernt. Der Algorithmus, den ich habe, funktioniert, aber er funktioniert nicht so, wie ich es beabsichtige.

Ich versuche, itertools zu stoppen, combinationssobald es zu einem Teilmengenprodukt der Eingabevariablen gelangt target. Dadurch wird der Code etwas schneller. Der Code befindet sich in der Polierphase, sodass eine unnötige Liste vorhanden istres_2

Hier ist die Schleife.

res_2 = [];
for i in range(1, len(s)+1):

   var = (findsubsets(s, i))   
   kk = list(map(numpy.prod, var))
   res_2.append(kk)
   if target in kk:
     print('yes')
     print(var)
     break

Dies ist die Ausgabe, die ich nicht möchte. Beachten Sie, dass das Skript nicht bei (4, 4) stoppt. Es ist eine Verschwendung von Ressourcen, weiterhin alle Kombinationen zu überprüfen, sobald ein Ziel "getroffen" wird.

Enter numbers WITH SPACES: 4 4 3 12
enter target integer:
16
yes
[(4, 4), (4, 3), (4, 12), (4, 3), (4, 12), (3, 12)]
 kk
[16, 12, 48, 12, 48, 36]

Meine beabsichtigte Ausgabe ist es, bei (4, 4) anzuhalten, wenn es der erste "Treffer" ist. Das gleiche gilt für jede andere Teilmenge wie (1,2,3) oder (1,2,3 --- beliebige Länge). Ich würde es vorziehen, wenn das Skript fortgesetzt wird, bis es einen Treffer findet. Sobald der Treffer gefunden wurde, stoppt er, da dies die Geschwindigkeit des Algorithmus verbessern würde.

Vollständiges Skript unten

# Naive Subset-Product solver
# with python's itertools

import itertools 
import numpy

s = list(map(int, input('Enter numbers WITH SPACES: ').split(' ')))
print('enter target integer: ')
target = int(input())


if s.count(target) > 0:
   print('yes')
   quit()

if target > numpy.prod(s):
  print('sorry cant be bigger than total product of s')
  quit()


def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

# Driver Code 
n = len(s)

# This code snippet is a for loop. It also is intended to cut down execution
# time once it finds the target integer. (instead of creating all combinations)

res_2 = [];
for i in range(1, len(s)+1):

   var = (findsubsets(s, i))   
   kk = list(map(numpy.prod, var))
   res_2.append(kk)
   if target in kk:
     print('yes')
     print(var)
     break

Frage

Wie kann ich das zum Laufen bringen, um die Geschwindigkeit des Algorithmus zu erhöhen? Welche pythonischen Tricks würden mein Problem beheben? Gibt es einen kürzeren Weg, dies zu tun?

Es ist verfrüht, den Rückgabewert der itertools combinationsin a umzuwandeln list, insbesondere wenn Sie versuchen, vorzeitig zu beenden und zu viel Overhead zu vermeiden. Es gibt normalerweise einen guten Grund, warum Bibliotheksfunktionen eher Iteratoren als vollständig realisierte Listen zurückgeben.

Hier ist ein Vorschlag:

def findsubsets(s, n): 
    return itertools.combinations(s, n)

def find_subset(target,nums):
    for i in range(1,len(nums)+1):
        for ss in findsubsets(nums, i):
            if np.prod(ss) == target:
                prodstr = '*'.join(str(num) for num in ss)
                print(f"{target} = {prodstr}")
                return ss
    return None

find_subset(96,[1,6,2,8])

Da es sich findsubsetsum eine einzelne Zeile handelt, ist es fraglich, sie als eigenständige Funktion zu verwenden (wir sind im Grunde nur ein Aliasing, combinationsdas mit einer import X as YAnweisung hätte durchgeführt werden können). In jedem Fall sollte dies frühzeitig aufhören, ohne zu viel RAM mit größeren Eingängen zu belasten.