A Combinaisons d'éléments dans la liste donnée

Question

Je suis actuellement en pays Python. C'est ce que je dois faire. J'ai déjà regardé dans la bibliothèque d'itertools mais il semble faire seulement des permutations.

Je veux prendre une liste d'entrée, comme [ « Yahoo », « wikipedia », « freebase »] et de générer chaque combinaison unique d'un élément avec zéro ou plusieurs autres articles ...

['yahoo', 'wikipedia', 'freebase'] 
['yahoo', 'wikipedia'] 
['yahoo', 'freebase'] 
['wikipedia', 'freebase'] 
['yahoo'] 
['freebase'] 
['wikipedia'] 

Quelques notes L'ordre n'a pas d'importance et j'essaye de concevoir la méthode pour prendre une liste de n'importe quelle taille. Aussi, y a-t-il un nom pour ce genre de combinaison?

Merci pour votre aide!

Answer 1

>>> l = ['yahoo', 'wikipedia', 'freebase'] 
>>> import itertools 
>>> for i in range(1, len(l) +1): 
    print(list(itertools.combinations(l, r=i))) 


[('yahoo',), ('wikipedia',), ('freebase',)] 
[('yahoo', 'wikipedia'), ('yahoo', 'freebase'), ('wikipedia', 'freebase')] 
[('yahoo', 'wikipedia', 'freebase')] 

post-scriptum Pourquoi ce wiki?

Answer 2

C'est ce qu'on appelle un ensemble d'alimentation. Suivez simplement ceci algorithm. Voici une implémentation simple:

def powerset(seq): 
    if len(seq): 
    head = powerset(seq[:-1]) 
    return head + [item + [seq[-1]] for item in head] 
    else: 
    return [[]] 

>>> powerset(['yahoo', 'wikipedia', 'freebase']) 
[[], ['yahoo'], ['wikipedia'], ['yahoo', 'wikipedia'], ['freebase'], ['yahoo', 'freebase'], ['wikipedia', 'freebase'], ['yahoo', 'wikipedia', 'freebase']] 

Et un autre:

def powerset(s): 
    sets = [] 
    indicator = lambda x: x & 1 
    for element in xrange(2**len(s)): 
    n = element 
    subset = [] 
    for x in s: 
     if indicator(n): 
      subset.append(x) 
     n >>= 1 
    sets.append(subset) 
    return sets 

Answer 3

Vous comptez essentiellement du 1 au 2 ⁿ -1 en binaire:

0 0 1 ['freebase'] 
0 1 0 ['wikipedia'] 
0 1 1 ['wikipedia', 'freebase'] 
1 0 0 ['yahoo'] 
1 0 1 ['yahoo', 'freebase'] 
1 1 0 ['yahoo', 'wikipedia'] 
1 1 1 ['yahoo', 'wikipedia', 'freebase'] 

Answer 4

Il a appelé un powerset. Ceci est une implémentation du itertools docs:

def powerset(iterable): 
    "powerset([1,2,3]) -->() (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))