¿Cuál es la forma más eficiente de generar las combinaciones de un conjunto en python?

Question

Este es el código que ocurrió:

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

Este algoritmo es O (n^2) el tiempo, pero se puede reducir el espacio? Escuché que usar yield podría funcionar, pero teniendo problemas para pensar cómo implementarlo con yield. No use la función de combinación incorporada. Me gustaría ver cómo se implementa.

Answer 1

Su pregunta específicamente dijo que quería ver lo que el código se vería así, por lo que aquí es un ejemplo de código de la mano de una solución de espacio de 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 

tenga en cuenta que la aritmética subcadena puede ser caro (ya que tiene que copiar la cadena muchas veces), por lo que aquí es una versión ligeramente más eficiente en términos de complejidad:

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 

no estoy usando Python 3.2, pero si se podría escribir así:

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) 

También debo señalar que esto es puramente académica desde itertools.combinations hace un buen trabajo y trabaja para una más amplia conjunto de entradas (incluidas las expresiones del generador).

Answer 2

Algo así debe hacerlo:

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

Answer 3

Puede utilizar yield en el código de este 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 

Pero no te salva cualquier espacio.

El itertools.combinations documentation muestra un algoritmo (mucho) más complicado que funciona en un espacio constante: el actual implementation está en C, pero dice ser equivalente.