generiert alle Kombinationen von zwei Listen und gibt sie eines nach der anderen in Python

Question

Ich habe zwei Listen

[1, 3, 4] [7, 8] 

Ich möchte alle Kombinationen von zwei Listen aus den kleinsten Kombinationen Ausgang wie 17,18,37,38,47,48,137,138,147,148......178,378.... für jeden Jetzt erzeugen Kombination muss ich es an einem anderen Ort testen und wenn ich diese Kombination gefunden habe, werde ich die Kombinationsgeneration stoppen. Zum Beispiel Wenn ich sehe, dass vorhanden ist, dann werde ich die anderen Kombinationen nicht erzeugen. Wenn ich 48 gefunden habe, werde ich die späteren Kombinationen nicht generieren.

Answer 1

Dies ist ein ziemlich hässlicher Algorithmus, aber es hat für mich funktioniert. Es ist auch nicht super teuer (erwarten, natürlich, für die Erzeugung aller Kombinationen mit itertools.combinations (a, i) ...):

import itertools 

def all_combs(a): 
    to_return = [] 
    temp = [] 
    for i in a: 
     temp.append(i) 
    to_return.append(temp) 
    for i in range(2, len(a) + 1): 
     temp = [] 
     for j in itertools.combinations(a, i): 
      s = "" 
      for k in j: 
       s = s + str(k) 
      temp.append(int(s)) #Get all values from the list permutation 
     to_return.append(temp) 
    print(to_return) 
    return to_return 

def all_perm(a, b): 
    a_combs = all_combs(a) 
    b_combs = all_combs(b) 
    to_return = [] 
    for i in a_combs: 
     for j in b_combs: 
      for k in i: 
       for l in j: 
        to_return.append(10**len(str(l)) * k + l) 
    to_return.sort() 
    for i in to_return: 
     yield i 

EDIT: Ein Fehler wurde behoben, wo Werte mehrstellige waren nicht richtig gelesen EDIT in: die Funktion wirken als Generator bearbeitet: ein Fehler wurde behoben Beteiligung Ziffern (durch eine Art Zugabe ...)

EDIT: Hier ist ein weit überlegen Implementierung ist, die eng um den Generator Stil viel mehr erfüllt. Es ist immer noch nicht perfekt, aber es sollte eine gute Beschleunigung im durchschnittlichen Fall bieten:

import itertools 

def add_to_dict(dict, length, num): 
    if not length in dict: 
     dict[length] = [] 
    dict[length].append(num) 

def sum_to_val(val): 
    to_return = [] 
    for i in range(1, val): 
     to_return.append([i, val-i]) 
    return to_return 

def all_combs(a): 
    to_return = {} 
    for i in a: 
     add_to_dict(to_return, len(str(i)), i) 
    for i in range(2, len(a) + 1): 
     for j in itertools.combinations(a, i): 
      s = "" 
      for k in j: 
       s = s + str(k) 
      add_to_dict(to_return, len(s), int(s)) #Get all values from the list permutation 
    return to_return 

def all_perm(a, b): 
    a_combs = all_combs(a) 
    b_combs = all_combs(b) 
    for val in range(max(a_combs.keys())+max(b_combs.keys())+1): 
     to_return = [] 
     sums = sum_to_val(val) 
     for i in sums: 
      if not(i[0] in a_combs and i[1] in b_combs): 
       continue 
      for j in a_combs[i[0]]: 
       for k in b_combs[i[1]]: 
        to_return.append(10**len(str(k)) * j + k) 
     to_return.sort() 
     for i in to_return: 
      yield i