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

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

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

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

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

  • Математическое управление уравнениями в Python
  • вопрос с нарезкой вставки, L
  • Лучший способ сделать флажок-логин login_required по умолчанию
  • Что такое принцип EAFP в Python?
  • Запуск от 1 до бесконечности в Python
  • Как установить Pillow на Windows с помощью pip?
  • Как скопировать функцию-член другого класса в myclass в python?
  • Как создать файл яйца Python
  • 15 Solutions collect form web for “Как получить все возможные комбинации элементов списка?”

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

     itertools.combinations(iterable, r) 

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

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

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

    Этот ответ пропустил один аспект: ОП запросил ВСЕ комбинации … не только комбинации длины «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) 

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

     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 -> ac 110 -> ab 111 -> abc 

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

    • Это требует, чтобы вы могли вызывать len(...) на items (обходной путь: если items являются чем-то вроде итерабельного типа генератора, сначала переведите его в список с items=list(_itemsArg) )
    • Это требует, чтобы порядок итераций по items не был случайным (обходной путь: не сумасшедший)
    • Для этого требуется, чтобы элементы были уникальными, иначе {2,2,1} и {2,1,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'}] 

    Здесь используется рекурсия:

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

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

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

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

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

     from itertools import combinations input = ['a', 'b', 'c', 'd'] output = sum([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

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

    Примечание . Если цель, s = list(iterable) , состоит в том, чтобы получить только комбинации уникальных элементов, измените строку 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) 

    Вы можете создать все комбинации списка в 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)] 

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

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

    Ниже приведен «стандартный рекурсивный ответ», похожий на другой аналогичный ответ https://stackoverflow.com/a/23743696/711085 . (Мы реально не должны беспокоиться о том, чтобы бежать из пространства стека, поскольку мы не можем обработать все перестановки N !.)

    Он посещает каждый элемент в свою очередь, и либо берет его, либо оставляет его (мы можем прямо видеть мощность 2 ^ N от этого алгоритма).

     def combs(xs, i=0): if i==len(xs): yield () return for c in combs(xs,i+1): yield c yield c+(xs[i],) 

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

     >>> list( combs(range(5)) ) [(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)] >>> list(sorted( combs(range(5)), key=len)) [(), (0,), (1,), (2,), (3,), (4,), (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3), (2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2), (3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)] >>> len(set(combs(range(5)))) 32 

    Я думал, что добавлю эту функцию для тех, кто ищет ответ, не импортируя 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 данные 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]

    Использование списка:

     def selfCombine( list2Combine, length ): listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \ + 'for i0 in range(len( list2Combine ) )' if length > 1: listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\ .replace( "', '", ' ' )\ .replace( "['", '' )\ .replace( "']", '' ) listCombined = '[' + listCombined + ']' listCombined = eval( listCombined ) return listCombined list2Combine = ['A', 'B', 'C'] listCombined = selfCombine( list2Combine, 2 ) 

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

     ['A', 'A'] ['A', 'B'] ['A', 'C'] ['B', 'B'] ['B', 'C'] ['C', 'C'] 
     def combinations(iterable, r): # combinations('ABCD', 2) --> AB AC AD BC BD CD # combinations(range(4), 3) --> 012 013 023 123 pool = tuple(iterable) n = len(pool) if r > n: return indices = range(r) yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != i + n - r: break else: return indices[i] += 1 for j in range(i+1, r): indices[j] = indices[j-1] + 1 yield tuple(pool[i] for i in indices) x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9] for i in combinations(x, 2): print i 

    Этот код использует простой алгоритм с вложенными списками …

     # FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists... # # [ [ [] ] ] # [ [ [] ], [ [A] ] ] # [ [ [] ], [ [A],[B] ], [ [A,B] ] ] # [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ] # [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ] # # There is a set of lists for each number of items that will occur in a combo (including an empty set). # For each additional item, begin at the back of the list by adding an empty list, then taking the set of # lists in the previous column (eg, in the last list, for sets of 3 items you take the existing set of # 3-item lists and append to it additional lists created by appending the item (4) to the lists in the # next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat # for each set of lists back to the initial list containing just the empty list. # def getCombos(listIn = ['A','B','C','D','E','F'] ): listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list listSimple = [] # list to contain the final returned list of items (eg, characters) for item in listIn: listCombos.append([]) # append an emtpy list to the end for each new item added for index in xrange(len(listCombos)-1, 0, -1): # set the index range to work through the list for listPrev in listCombos[index-1]: # retrieve the lists from the previous column listCur = listPrev[:] # create a new temporary list object to update listCur.append(item) # add the item to the previous list to make it current listCombos[index].append(listCur) # list length and append it to the current list itemCombo = '' # Create a str to concatenate list items into a str for item in listCur: # concatenate the members of the lists to create itemCombo += item # create a string of items listSimple.append(itemCombo) # add to the final output list return [listSimple, listCombos] # END getCombos() 

    Это моя реализация

      def get_combinations(list_of_things): """gets every combination of things in a list returned as a list of lists Should be read : add all combinations of a certain size to the end of a list for every possible size in the the list_of_things. """ list_of_combinations = [list(combinations_of_a_certain_size) for possible_size_of_combinations in range(1, len(list_of_things)) for combinations_of_a_certain_size in itertools.combinations(list_of_things, possible_size_of_combinations)] return list_of_combinations 
    Interesting Posts

    Есть ли способ получить ваш адрес электронной почты после аутентификации с помощью Gmail с помощью Oauth?

    Различное поведение для списка .__ iadd__ и list .__ add__

    python pandas извлекает уникальные даты из временных рядов

    Использование заголовков с методом получения библиотеки запросов Python

    Проверьте, находится ли float рядом с любым поплавком, хранящимся в массиве

    Не удается запустить консоль в недавно установленном Pycharm в Windows

    Есть ли карта без результата в python?

    Проверка делимости на несколько номеров

    Оператор overload () в Python

    Python Pandas, используя предыдущее значение в Dataframe

    Применение цветного наложения к изображению в PIL или Imagemagik

    Нужен ли нам файл sconscript в каждом исходном каталоге

    данные о рассеянном участке не отображаются на континентах в базовой карте «молоток»

    Вызов функций python из * .py файлов из java и передачи и возврата

    Какая хорошая двухсторонняя библиотека шифрования реализована в Python?

    Python - лучший язык программирования в мире.