一個生成所有兩個列表他們一個輸出組合，並在python

-1

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

我要生成的兩個列表從最小的組合開始像17,18,37,38,47,48,137,138,147,148......178,378.... 現在，每一個所有組合我必須在其他地方測試它的存在，如果我發現組合存在，那麼我將停止組合生成。例如，如果我看到17存在，那麼我將不會生成其他組合。再次如果我發現48存在，那麼我將不會生成後面的組合。

來源

2016-07-25 tanay

我們不會爲你做你的功課。 –

如果你想幫助一個家庭作業問題（我猜這是什麼），確保包括你迄今爲止所做的，並尋求建議，而不是解決方案。我會推薦閱讀這篇文章：http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions或this：http://meta.stackoverflow.com/questions/ 253792/stack-overflow-and-homework-questions – Checkmate

這不是一項家庭作業。這是我正在做的一個項目的一部分。我需要從兩個列表中逐個生成所有組合。我只是問是否有任何有效的方法來做到這一點，因爲我正在做的是效率不高...... – tanay

這是一個非常醜陋的算法，但它爲我工作。它也沒有超貴（期待，當然，對於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

編輯：修正了一個多位數的值不讀取正確編輯：製造功能充當發電機編輯：（通過sort ...）修正涉及數字的錯誤

編輯：這裏是一個大大優於實施這更符合發電機風格緊密結合。它仍然不是完美的，但它應該在平均情況下提供良好的加速：

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

來源

2016-07-25 18:08:01 Checkmate

@tanay您可能已經發現這個，但是這段代碼有一個bug。我添加了一個sort（）來修復它，但是對於大型列表來說這可能會很慢。我會找到更好的解決方案。 – Checkmate

嗯，經過測試，將所有值放入to_return並對其進行排序所需的時間是非常不可接受的。讓我知道如果這對你是一個問題，我可以重寫算法來避免這種情況。 – Checkmate

對不起，延遲迴復..我實際上修改了一點算法。我不想預先製作這兩個列表的所有組合，因爲如果我得到組合的匹配，那麼我將停止循環。所以我只爲一個列表進行預生產，然後通過另一個列表並根據需要生成組合。當我得到一個比賽組合我停在那裏.. – tanay

一個生成所有兩個列表他們一個輸出組合，並在python

回答

相關問題