Составление всех возможных комбинаций списка

Question

Мне нужно составить список, содержащий все возможные комбинации введенного списка.Например, список [1,2,3] должен возвращать [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] Список не должен быть в каком-то определенном порядке.На этом сайте я нашел много функций, использующих itertools, но они возвращают объекты, когда мне нужен только list.

Answer 1

Просто используйте itertools.combinations.Например:

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)

Теперь combs содержит это значение:

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

Да, оно немного отличается от предоставленного вами примера вывода, но в этом выводе вы не отображалисьвсе возможные комбинации.

Я перечисляю размер комбинации перед фактическим списком для каждого размера, если вам нужны просто комбинации (без размера, как это показано вваш пример вывода), затем попробуйте следующую версию кода:

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)

Теперь combs содержит это значение:

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

Answer 2

Модуль itertools действительно возвращает генераторы вместо списков, но:

• Генераторы часто более эффективны, чем списки (особенно если вы генерируете большое количество комбинаций)
• Вы всегда можете преобразовать генераторы в списки, используя list(...), когда вам действительно нужно.

chain и combinationsфункции itertools работают хорошо , но вам нужно использовать Python 2.6 или более поздней версии:

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)))

Затем вы можете назвать это так:

# 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]]

Если вы ранее не использовали генераторы, обратите внимание, что вы просматриваете их, как если бы они были списком, например:

# 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)
"""

Разница в производительности может быть существенной. Если вы сравните производительность, вы увидите, что генератор гораздо быстрее создать:

# 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

Обратите внимание, что в любом случае для перебора всех комбинаций потребуется некоторое время, но это может бытьбольшая победа для вас, особенно если вы найдете то, что ищете Эрлу вкл.

Answer 3

Вы можете решить вашу проблему, используя itertools.combinations внутри цикла:

>>> 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)]

А если вы хотите, чтобы они были в списке:

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

РЕДАКТИРОВАТЬ: Первый параметр комбинаций является итеративным, а второй - длиной результирующих кортежей (в данном случае от 1 до len(l)).

Подробнее о комбинациях: http://docs.python.org/library/itertools.html#itertools.combinations

Answer 4

Функции из модуля itertools возвращают итераторы.Все, что вам нужно сделать, чтобы преобразовать их в списки, это вызвать list() для результата.

Однако, поскольку вам нужно будет вызвать itertools.combinations три раза (по одному разу для каждой другой длины), вы можете простоиспользуйте list.extend, чтобы добавить все элементы итератора в ваш окончательный список.

Попробуйте выполнить следующее:

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))

Или как понимание списка:

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

Это приведет к следующему списку:

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

Если вы хотите использовать списки вместо кортежей и преобразовать кортежи одинарной длины в просто значение, вы можете сделать следующее:

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]]

Или оставить отдельные элементы в виде списков:

out_list = map(list, out_list)

Answer 5

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

Если вы хотите использовать oneliner.

Answer 6

Я думаю, что здесь стоит свести остальные ответы в простой пример Python 3:

from itertools import chain, combinations

def all_combinations(array):
    return chain(*(list(combinations(array, i + 1)) for i in range(len(array))))

Возвращает итерацию для просмотра значений:

>>> print(list(all_combinations((1, 2, 3))))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]