getting every possible combination in a list
and I wanted to get every combination of files without repeating combinations that have already been done (once cat_dog is done do not do dog_cat again). Is there a way I could do this? My real list is in alphabetical order, if that makes any difference.
This has been asked plenty of times so will probably get closed. import itertools; itertools.combinations([‘cat’, ‘dog’, ‘fish’], 2)
6 Answers 6
In reality what you’re asking how to do is produce all combinations of two items taken in the list of names (as opposed to all the possible combination of them).
That means you can use the built-in itertools.combinations() generator function to easily (and efficiently) generate pairs of the names you want with no repeats:
L1 = ['cat', 'dog', 'fish', 'rabbit', 'horse', 'bird', 'frog', 'mouse'] for pair in combinations(L1, 2): print(pair) input1 = open('file_%s' % pair[0], 'r') input2 = open('file_%s' % pair[1], 'r') ('cat', 'dog') ('cat', 'fish') ('cat', 'rabbit') ('cat', 'horse') ('cat', 'bird') ('cat', 'frog') ('cat', 'mouse') ('dog', 'fish') ('dog', 'rabbit') ('dog', 'horse') ('dog', 'bird') ('dog', 'frog') ('dog', 'mouse') ('fish', 'rabbit') ('fish', 'horse') ('fish', 'bird') ('fish', 'frog') ('fish', 'mouse') ('rabbit', 'horse') ('rabbit', 'bird') ('rabbit', 'frog') ('rabbit', 'mouse') ('horse', 'bird') ('horse', 'frog') ('horse', 'mouse') ('bird', 'frog') ('bird', 'mouse') ('frog', 'mouse') All combinations of a list of lists [duplicate]
I’m basically looking for a python version of Combination of List> Given a list of lists, I need a new list that gives all the possible combinations of items between the lists.
The number of lists is unknown, so I need something that works for all cases. Bonus points for elegance!
9 Answers 9
>>> import itertools >>> a = [[1,2,3],[4,5,6],[7,8,9,10]] >>> list(itertools.product(*a)) [(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)] *a means these are arguments being passed to the function or method. def fn(a,b,c): would respond to fn(*[1,2,3]) reference
@mjallday, would it be possible to add also these combinations: (7,4,1),(8,4,1),(9,4,1),(10,4,1),(7,5,1),(8,5,1),(9,5,1),(10,5,1) etc?
@Reman It’s not entirely clear what you want to get but if it is, for example, also the reverse of each tuple you can use a a wrapper function that takes a as input, iterates over itertools.product(*a) and yield s both the tuple produced by itertools and a reverse version (e.g. create a list, reverse() it and convert back to tuple). Best ask a new question.
if you are familiar with javascript [*a] would be the same the js spread operator [. a] . This is also true for dicts
The most elegant solution is to use itertools.product in python 2.6.
If you aren’t using Python 2.6, the docs for itertools.product actually show an equivalent function to do the product the «manual» way:
def product(*args, **kwds): # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 pools = map(tuple, args) * kwds.get('repeat', 1) result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod) Simply use itertools.product :
listOLists = [[1,2,3],[4,5,6],[7,8,9,10]] for l in itertools.product(*listOLists): print(l) Nothing wrong with straight up recursion for this task, no need for external dependencies, and if you need a version that works with strings, this might fit your needs:
combinations = [] def combine(terms, accum): last = (len(terms) == 1) n = len(terms[0]) for i in range(n): item = accum + terms[0][i] if last: combinations.append(item) else: combine(terms[1:], item) >>> a = [['ab','cd','ef'],['12','34','56']] >>> combine(a, '') >>> print(combinations) ['ab12', 'ab34', 'ab56', 'cd12', 'cd34', 'cd56', 'ef12', 'ef34', 'ef56'] >>> import numpy >>> a = [[1,2,3],[4,5,6],[7,8,9,10]] >>> [list(x) for x in numpy.array(numpy.meshgrid(*a)).T.reshape(-1,len(a))] [[ 1, 4, 7], [1, 5, 7], [1, 6, 7], . ] this feels like asking ‘how do i boil water’ and instead of saying ‘use a kettle’, you get ‘lower the atmospheric pressure around the water’. Both work!
One can use base python for this. The code needs a function to flatten lists of lists:
def flatten(B): # function needed for code below; A = [] for i in B: if type(i) == list: A.extend(i) else: A.append(i) return A L = [[1,2,3],[4,5,6],[7,8,9,10]] outlist =[]; templist =[[]] for sublist in L: outlist = templist; templist = [[]] for sitem in sublist: for oitem in outlist: newitem = [oitem] if newitem == [[]]: newitem = [sitem] else: newitem = [newitem[0], sitem] templist.append(flatten(newitem)) outlist = list(filter(lambda x: len(x)==len(L), templist)) # remove some partial lists that also creep in; print(outlist) [[1, 4, 7], [2, 4, 7], [3, 4, 7], [1, 5, 7], [2, 5, 7], [3, 5, 7], [1, 6, 7], [2, 6, 7], [3, 6, 7], [1, 4, 8], [2, 4, 8], [3, 4, 8], [1, 5, 8], [2, 5, 8], [3, 5, 8], [1, 6, 8], [2, 6, 8], [3, 6, 8], [1, 4, 9], [2, 4, 9], [3, 4, 9], [1, 5, 9], [2, 5, 9], [3, 5, 9], [1, 6, 9], [2, 6, 9], [3, 6, 9], [1, 4, 10], [2, 4, 10], [3, 4, 10], [1, 5, 10], [2, 5, 10], [3, 5, 10], [1, 6, 10], [2, 6, 10], [3, 6, 10]] This mostly mimics solutions like Answer by Jarret Hardie using itertools.product, but has these distinctions:
- this passes parameters to itertools.product in-line, instead of via variable a — so no *args syntax needed on the inline parameters
- if your mypy type-linter acts like mine, and you can get your code to otherwise «work» with the *args syntax with inline product parameters (like product(*[[1,2,3],[4,5,6],[7,8,9,10]]) ), mypy might still fail it (with something like error: No overload variant of «product» matches argument type «List[object]» )
- So solution to that mypy , is to not use *args syntax, like this:
>>> import itertools >>> list(itertools.product([1,2,3],[4,5,6],[7,8,9,10])) [(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)] This answer isn’t as clean as using itertools but the ideas could be useful.
Drawing inspiration from the construction of zip() here, we could do the following.
>>> a = iter([[1,2,3],[4,5,6],[7,8,9,10]]) >>> sentinel = object() >>> result = [[]] >>> while True: >>> l = next(a,sentinel) >>> if l == sentinel: >>> break >>> result = [ r + [digit] for r in result for digit in l] >>> print(result) [[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 4, 10], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 5, 10], [1, 6, 7], [1, 6, 8], [1, 6, 9], [1, 6, 10], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 4, 10], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 5, 10], [2, 6, 7], [2, 6, 8], [2, 6, 9], [2, 6, 10], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 4, 10], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 5, 10], [3, 6, 7], [3, 6, 8], [3, 6, 9], [3, 6, 10]] We use a as an iterator in order to successively get the next item of it without needing to know how many there are a priori. The next command will output sentinel (which is an object created solely to make this comparison, see here for some explanation) when we run out of lists in a , causing the if statement to trigger so we break out of the loop.
Generating all possible combinations of a list, «itertools.combinations» misses some results
Given a list of items in Python, how can I get all the possible combinations of the items? There are several similar questions on this site, that suggest using itertools.combinations , but that returns only a subset of what I need:
stuff = [1, 2, 3] for L in range(0, len(stuff)+1): for subset in itertools.combinations(stuff, L): print(subset) () (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3) As you see, it returns only items in a strict order, not returning (2, 1) , (3, 2) , (3, 1) , (2, 1, 3) , (3, 1, 2) , (2, 3, 1) , and (3, 2, 1) . Is there some workaround for that? I can’t seem to come up with anything.
7 Answers 7
>>> import itertools >>> stuff = [1, 2, 3] >>> for L in range(0, len(stuff)+1): for subset in itertools.permutations(stuff, L): print(subset) . () (1,) (2,) (3,) (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) . Help on itertools.permutations :
permutations(iterable[, r]) --> permutations object Return successive r-length permutations of elements in the iterable. permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1) You can generate all the combinations of a list in python using this simple code
import itertools a = [1,2,3,4] for i in xrange(1,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)] Even though the question has «combinations» in it, what is meant is permutations. Read it till the end and see that both (2, 1) and (1, 2) are expected from OP.
Are you looking for itertools.permutations instead?
Help on class permutations in module itertools: class permutations(__builtin__.object) | permutations(iterable[, r]) --> permutations object | | Return successive r-length permutations of elements in the iterable. | | permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1) >>> from itertools import permutations >>> stuff = [1, 2, 3] >>> for i in range(0, len(stuff)+1): for subset in permutations(stuff, i): print(subset) () (1,) (2,) (3,) (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) From Wikipedia, the difference between permutations and combinations :
Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set , namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).
In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.