Qual è il modo più efficiente in termini di memoria per generare le combinazioni di un set in python?

Question

Questo è il codice mi si avvicinò con:

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

Questo algoritmo è O (2^n), ma può essere ridotto lo spazio? Ho sentito che usare yield potrebbe funzionare, ma ho problemi a pensare a come implementare con yield. Si prega di non utilizzare la funzione di combinazione integrata - Mi piacerebbe vedere come è implementato.

Answer 1

La tua domanda specificamente detto che volevi vedere ciò che il codice sarà simile, ecco una mano esempio codificato di un O (n) soluzione di spazio:

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 

Nota che la stringa aritmetica potrebbe essere costoso (in quanto si deve copiare la stringa molte volte), ecco una versione leggermente più efficiente in termini di complessità:

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 

non sto usando Python 3.2, ma se tu fossi si può scrivere in questo modo:

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) 

Si noti anche che questo è puramente accademica in quanto itertools.combinations fa un ottimo lavoro e lavora per una più ampia array di input (incluse le espressioni del generatore).

Answer 2

Qualcosa del genere dovrebbe farlo:

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

Answer 3

È possibile utilizzare yield nel codice in questo modo:

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

Ma non ti salvare qualsiasi spazio.

Il itertools.combinations documentation mostra un algoritmo (molto) più complicato che funziona in uno spazio costante - lo actual implementation è in C, ma afferma di essere equivalente.