Quel est le moyen le plus efficace en mémoire de générer les combinaisons d'un ensemble en python?

Question

Ceci est le code que je suis venu avec:

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

Cet algorithme est O (2^n), mais peut être un espace réduit? J'ai entendu utiliser yield pourrait fonctionner, mais avoir du mal à réfléchir à la façon de mettre en œuvre avec yield. S'il vous plaît ne pas utiliser la fonction de combinaison intégrée - je voudrais voir comment il est mis en œuvre.

Answer 1

Votre question dit que vous vouliez voir précisément ce que le code ressemblerait, alors voici un exemple codé à la main d'une solution d'espace 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 

Notez que l'arithmétique sous-chaîne pourrait être coûteuse (car il doit copier la chaîne à plusieurs reprises), alors voici une version légèrement plus efficace en termes de complexité:

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 

Je ne suis pas en Python 3.2, mais si vous étiez vous pourriez écrire comme ceci:

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) 

Je tiens également à noter que cela est purement théorique puisque itertools.combinations fait un excellent travail et travaille pour une plus large tableau d'entrées (y compris les expressions de générateur).

Answer 2

Quelque chose comme ça devrait le faire:

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

Answer 3

Vous pouvez utiliser yield dans votre code comme ceci:

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

Mais il ne vous sauvera pas d'espace.

Le itertools.combinations documentation montre un algorithme (beaucoup) plus compliqué qui fonctionne dans l'espace constant - le actual implementation est en C, mais prétend être équivalent.