在python中生成一個組合的最有效的方法是什麼？

Question

這是我想出的代碼：

def combinations(input): 
    ret = [''] 
    for i in range(len(input)): 
     ret.extend([prefix+input[i] for prefix in ret]) 
    return ret 

該算法O（2^n）的時間，但可空間被減小？我聽說使用yield可能會工作，但無法思考如何使用yield來實現。請不要使用內置的組合功能 - 我想看看它是如何實現的。

Answer 1

你的問題具體說你想看到的代碼是什麼樣子，所以這裏是一個O（n）的空間解決方案的手工編碼例如：

def combinations(input_list, acc=''): 

    if not input_list: 
     yield acc 
     return 

    next_val = input_list[0] 

    for rest in combinations(input_list[1:], acc): 
     yield rest 

    acc += next_val 

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)" 
    for rest in combinations(input_list[1:], acc): 
     yield rest 

注意，子算術可能是昂貴的（因爲它有字符串多次複製），所以這裏是在複雜性方面稍微更有效的版本：

def combinations(input_list, acc='', from_idx=0): 

    if len(input_list) <= from_idx: 
     yield acc 
     return 

    next_val = input_list[from_idx] 

    for rest in combinations(input_list, acc, from_idx + 1): 
     yield rest 

    acc += next_val 

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)" 
    for rest in combinations(input_list, acc, from_idx + 1): 
     yield rest 

我不使用Python 3.2，但如果你是，你可以寫這樣的：

def combinations(input_list, acc='', from_idx=0): 

    if len(input_list) <= from_idx: 
     yield acc 
     return 

    next_val = input_list[from_idx] 

    yield from combinations(input_list, acc, from_idx + 1) 
    acc += next_val 
    yield from combinations(input_list, acc, from_idx + 1) 

我也應該注意到，這是純學術的，因爲itertools.combinations做了很好的工作，適用於更廣泛的輸入數組（包括生成器表達式）。

Answer 2

像這樣的東西應該這樣做：

>>> print list(itertools.combinations({1, 2, 3, 4}, 3)) 
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)] 
>>> 

Answer 3

您可以在代碼中使用yield像這樣：

def combinations(input): 
    ret = [''] 
    yield '' 
    for i in range(len(input)): 
     for prefix in ret: 
      combination = prefix+input[i] 
      ret.extend(combination) 
      yield combination 

但它不保存你任何空間。

itertools.combinations documentation顯示了一個（很多）更復雜的算法，它可以在恆定的空間中工作 - actual implementation在C中，但聲稱是等價的。