All combinations of list wIthout itertools
I’m trying to make a recursive function that finds all the combinations of a python list. I want to input [‘a’,’b’,’c’] in my function and as the function runs I want the trace to look like this:
['a','b','c'] ['['a','a'],['b','a'],['c','a']] ['['a','a','b'],['b','a','b'],['c','a','b']] ['['a','a','b','c'],['b','a','b','c'],['c','a','b','c']] def combo(lst,new_lst = []): for item in lst: new_lst.append([lst[0],item]) print([lst[0],item]) return combo(new_lst,lst[1:]) Your expected output does not makes sense. How did you get [‘a’,’a’,’b’,’c’] or [‘a’,’a’] ? Why two ‘a’ there?
2 Answers 2
The right answer is that you should use itertools.combinations . But if for some reason you don’t want to, and want to write a recursive function, you can use the following piece of code. It is an adaptation of the erlang way of generating combinations, so it may seem a bit weird at first:
def combinations(N, iterable): if not N: return [[]] if not iterable: return [] head = [iterable[0]] tail = iterable[1:] new_comb = [ head + list_ for list_ in combinations(N - 1, tail) ] return new_comb + combinations(N, tail) This a very elegant way of thinking of combinations of size N : you take the first element of an iterable (head) and combine it with smaller ( N-1 ) combinations of the rest of the iterable (tail). Then you add same size ( N ) combinations of the tail to that. That’s how you get all possible combinations.
If you need all combinations, of all lengths you would do:
for n in range(1, len(iterable) + 1): print(combinations(n, iterable)) 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.
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') How to get all combinations of a list?
Use itertools.combinations and a simple loop to get combinations of all size.
combinations return an iterator so you’ve to pass it to list() to see it’s content(or consume it).
>>> from itertools import combinations >>> lis = [1, 2, 3, 4] for i in xrange(1, len(lis) + 1): # xrange will return the values 1,2,3,4 in this loop print list(combinations(lis, 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)] It sounds like you are actually looking for itertools.combinations() :
>>> from itertools import combinations >>> list(combinations([1, 2, 3, 4], 3)) [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)] This example also shows how to convert the result to a regular list, just pass it to the built-in list() function.
To get the combinations for each length you can just use a loop like the following:
>>> data = [1, 2, 3, 4] >>> for i in range(1, len(data)+1): . print list(combinations(data, 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)] Or to get the result as a nested list you can use a list comprehension:
>>> [list(combinations(data, i)) for i in range(1, len(data)+1)] [[(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)]] For a flat list instead of nested:
>>> [c for i in range(1, len(data)+1) for c in combinations(data, 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)]