Как получить все возможные комбинации элементов списка?

Question

У меня есть список с 15 числами, и мне нужно написать некоторый код, который производит все 32 768 комбинаций этих чисел.

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

Единственное, что мне приходит в голову, - это просто перебирать десятичные целые числа 1–32768 и преобразовывать их в двоичные, а также использовать двоичное представление в качестве фильтра для выбора соответствующих чисел.

Кто-нибудь знает лучший способ? Используя map(), может быть?

Answer 1

В этом ответе пропущен один аспект: ОП запросил ВСЕ комбинации ... а не только комбинации длины "r".

Так что вам придется либо пройти по всей длине "L":

import itertools

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

Или - если вы хотите придраться (или согнуть мозг того, кто читает ваш код после вас) - вы можете сгенерировать цепочку генераторов "комбинаций ()" и повторить это:

from itertools import chain, combinations
def all_subsets(ss):
    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))

for subset in all_subsets(stuff):
    print(subset)

Answer 2

Посмотрите на itertools.combinsk :

itertools.combinations(iterable, r)

Возвращает r длины подпоследовательностей элементов из ввод повторяемый.

Комбинации выводятся в лексикографическом порядке сортировки. Итак, если входной итерируемый сортируется, Комбинированные кортежи будут производиться в отсортированный заказ.

Начиная с версии 2.6, батареи включены!

Answer 3

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

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

Основная идея этого ответа: есть 2 ^ N комбинаций - столько же, сколько число двоичных строк длины N. Для каждой двоичной строки вы выбираете все элементы, соответствующие «1».

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

Что нужно учитывать:

• Для этого необходимо, чтобы вы вызывали len(...) на items (обходной путь: если items является чем-то вроде итерируемого как генератор, сначала включите его в список с items=list(_itemsArg))
• Это требует, чтобы порядок итерации на items не был случайным (обходной путь: не будьте безумным)
• Для этого необходимо, чтобы элементы были уникальными, иначе {2,2,1} и {2,1,1} оба свернутся до {2,1} (обходной путь: используйте collections.Counter в качестве замены для set; это в основном мультисеть. ... хотя вам, возможно, потребуется позже использовать tuple(sorted(Counter(...).elements())), если вам нужно, чтобы он был хэшируемым)

---

Демо

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

Answer 4

В комментариях под весьма одобренным ответом @Dan H, в документации itertools упоминается рецепт powerset(), включая один Dan сам . Однако , пока никто не опубликовал его в качестве ответа. Поскольку это, вероятно, один из лучших, если не самый лучший подход к проблеме, и, учитывая небольшое поощрение от другого комментатора, он показан ниже. Функция создает все уникальные комбинации элементов списка каждую возможную длину (включая те, которые содержат ноль и все элементы).

Примечание : Если цель, которая немного отличается, состоит в том, чтобы получить только комбинации уникальных элементов, измените строку s = list(iterable) на s = list(set(iterable)), чтобы исключить любые дублирующиеся элементы. Несмотря на это, тот факт, что iterable в конечном итоге превращается в list, означает, что он будет работать с генераторами (в отличие от некоторых других ответов).

from itertools import chain, combinations

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

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

Выход:

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)

Answer 5

Вот один, использующий рекурсию:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']

Answer 6

Этот однострочник дает вам все комбинации (от 0 до n элементов, если исходный список / набор содержит n различных элементов) и использует собственный метод itertools.combinations:

Python 2

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

Python 3

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])

---

Вывод будет:

[[],
 ['a'],
 ['b'],
 ['c'],
 ['d'],
 ['a', 'b'],
 ['a', 'c'],
 ['a', 'd'],
 ['b', 'c'],
 ['b', 'd'],
 ['c', 'd'],
 ['a', 'b', 'c'],
 ['a', 'b', 'd'],
 ['a', 'c', 'd'],
 ['b', 'c', 'd'],
 ['a', 'b', 'c', 'd']]

---

Попробуйте онлайн:

http://ideone.com/COghfX

Answer 7

Я согласен с Дэном Х., что Бен действительно попросил все комбинации. itertools.combinations() не дает всех комбинаций.

Другая проблема в том, что если итеративность ввода велика, возможно, лучше вернуть генератор вместо всего в списке:

iterable = range(10)
for s in xrange(len(iterable)+1):
  for comb in itertools.combinations(iterable, s):
    yield comb

Answer 8

Вы можете создать все комбинации списка в Python, используя этот простой код

import itertools

a = [1,2,3,4]
for i in xrange(0,len(a)+1):
   print list(itertools.combinations(a,i))

Результат будет:

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

Answer 9

Я думал, что добавлю эту функцию для тех, кто ищет ответ без импорта itertools или каких-либо других дополнительных библиотек.

def powerSet(items):
    """
    Power set generator: get all possible combinations of a list’s elements

    Input:
        items is a list
    Output:
        returns 2**n combination lists one at a time using a generator 

    Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
    """

    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

Генератор простого урожая Использование:

for i in powerSet([1,2,3,4]):
    print (i, ", ",  end="")

Вывод из примера использования выше:

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

Answer 10

Вот еще одно решение (однострочное), включающее использование функции itertools.combinations, но здесь мы используем понимание двойного списка (в отличие от цикла for или суммы):

def combs(x):
    return [c for i in range(len(x)+1) for c in combinations(x,i)]

---

Демо-версия:

>>> combs([1,2,3,4])
[(), 
 (1,), (2,), (3,), (4,), 
 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), 
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), 
 (1, 2, 3, 4)]