Tworzenie wszystkich możliwych kombinacji listy w pytonie

Question

Potrzebuję mieć możliwość utworzenia listy zawierającej wszystkie możliwe kombinacje wprowadzonej listy. Na przykład lista [1,2,3] powinna wrócić [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] Lista nie musi być w dowolnej kolejności. Na tej stronie znalazłem wiele funkcji za pomocą narzędzi itertools, ale są to zwracane obiekty, gdy potrzebuję tylko listy. Jestem początkującym programistą kodującym pythona, więc wszelkie przemyślenia i pomysły będą mile widziane.

Answer 1

Po prostu użyj itertools.combinations. Na przykład:

import itertools 

lst = [1, 2, 3] 
combs = [] 

for i in xrange(1, len(lst)+1): 
    combs.append(i) 
    els = [list(x) for x in itertools.combinations(lst, i)] 
    combs.append(els) 

Teraz combs utrzymuje tę wartość:

[1, [[1], [2], [3]], 2, [[1, 2], [1, 3], [2, 3]], 3, [[1, 2, 3]]] 

Tak, to jest nieco inny od wyjścia próbki podany, ale w tej produkcji nie zostały wymieniając wszystkie możliwe kombinacje.

Podajemy rozmiar kombinacji przed rzeczywistą listę dla każdego rozmiaru, jeśli to, czego potrzebujesz, to po prostu kombinacje (bez rozmiaru, jak to pojawia się w wynikach próbki), a następnie wypróbuj te inne wersje kod:

import itertools 

lst = [1, 2, 3] 
combs = [] 

for i in xrange(1, len(lst)+1): 
    els = [list(x) for x in itertools.combinations(lst, i)] 
    combs.extend(els) 

teraz combs utrzymuje tę wartość:

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

Answer 2

funkcje z tych iteratorów w obie strony modułu itertools. Wszystko, co musisz zrobić, aby przekształcić je w listy, to wywołanie list() na wyniku.

Ponieważ jednak będziesz musiał zadzwonić pod numer itertools.combinations w trzech oddzielnych odstępach czasu (jeden raz za każdą inną długość), możesz po prostu użyć list.extend, aby dodać wszystkie elementy iteratora do swojej ostatecznej listy.

Spróbuj wykonać następujące czynności:

import itertools 
in_list = [1, 2, 3] 
out_list = [] 
for i in range(1, len(in_list)+1): 
    out_list.extend(itertools.combinations(in_list, i)) 

lub jako listowego:

out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)] 

To spowoduje poniższej listy:

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

Jeśli chcesz list zamiast krotki , i do konwersji krotek jednej długości do wartości, można wykonać następujące czynności:

out_list = [x[0] if len(x) == 1 else list(x) for x in out_list] 
# [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

Albo zostawić pojedyncze elementy jak list:

Answer 3

Można rozwiązać problem przy użyciu itertools.combinations wewnątrz pętli:

>>> l = [1,2,3] 
>>> comb = [] 
>>> for i in range(len(l)): 
... comb += itertools.combinations(l,i+1) 
... 
>>> comb 
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

A jeśli chcesz je jako listę :

>>> comb_list = [ list(t) for t in comb ] 
>>> comb_list 
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

EDYTOWANIE: Pierwszy parametr kombinacji to iteracja, a drugi to długość wynikowych krotek (w tym przypadku przejście z 1 do len(l)).

Więcej o kombinacjach: http://docs.python.org/library/itertools.html#itertools.combinations

Answer 4

Moduł itertools rzeczywiście zwraca generatory zamiast list, ALE:

• Generatory są często bardziej wydajne niż listach (zwłaszcza jeśli generujących dużą liczbę kombinacje)
• Zawsze można przekonwertować generatory na listy przy użyciu list(...), kiedy naprawdę trzeba.

The chain i combinations funkcje itertools dobrze, ale trzeba użyć Python 2.6 lub większy:

import itertools 

def all_combinations(any_list): 
    return itertools.chain.from_iterable(
     itertools.combinations(any_list, i + 1) 
     for i in xrange(len(any_list))) 

Następnie można nazwać jako takie:

# as a generator 
all_combinations([1,2,3]) # --> <itertools.chain at 0x10ef7ce10> 

# as a list 
list(all_combinations([1,2,3])) # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

# as a list of lists 
[list(l) for l in all_combinations([1,2,3])] # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

Jeśli wcześniej nie korzystałeś z generatorów, pamiętaj, że je przeglądasz, jakby były T, taki jak poniżej:

# a generator returned instead of list 
my_combinations = all_combinations([1,2,3]) 

# this would also work if `my_combinations` were a list 
for c in my_combinations: 
    print "Combo", c 

""" 
Prints: 
    Combo (1,) 
    Combo (2,) 
    Combo (3,) 
    Combo (1, 2) 
    Combo (1, 3) 
    Combo (2, 3) 
    Combo (1, 2, 3) 
""" 

Różnica w wydajności może być dramatycznie. Jeśli porównać wydajność zobaczysz, że generator jest o wiele szybciej utworzyć:

# as a generator 
all_combinations(range(25)) # timing: 100000 loops, best of 3: 2.53 µs per loop 

# as a list 
list(all_combinations(range(25))) # timing: 1 loops, best of 3: 9.37 s per loop 

Zauważ, że to jeszcze trochę czasu na iterację wszystkich kombinacji w każdym przypadku, ale może to być duży wygrać dla Ciebie, zwłaszcza jeśli znajdziesz to, czego szukasz na początku.

Answer 5

l = [1,2,3] 
combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), []) 

Jeśli chcesz oneliner.