Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get all possible combinations of a list’s elements?

I have a list with 15 numbers in, and I need to write some code that produces all 32,768 combinations of those numbers.

I've found some code (by Googling) that apparently does what I'm looking for, but I found the code fairly opaque and am wary of using it. Plus I have a feeling there must be a more elegant solution.

The only thing that occurs to me would be to just loop through the decimal integers 1–32768 and convert those to binary, and use the binary representation as a filter to pick out the appropriate numbers.

Does anyone know of a better way? Using map(), maybe?

like image 762
Ben Avatar asked Jan 21 '09 11:01

Ben


People also ask

How do you find all possible combinations?

Combinations are a way to calculate the total outcomes of an event where order of the outcomes does not matter. To calculate combinations, we will use the formula nCr = n! / r! * (n - r)!, where n represents the total number of items, and r represents the number of items being chosen at a time.

How do you figure out the number of combinations with 4 numbers?

You multiply these choices together to get your result: 4 x 3 x 2 (x 1) = 24. Combinations and permutations are often confused by students - they are related, but they mean different things and can lead to totally different interpretations of situations and questions.


2 Answers

This answer missed one aspect: the OP asked for ALL combinations... not just combinations of length "r".

So you'd either have to loop through all lengths "L":

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

Or -- if you want to get snazzy (or bend the brain of whoever reads your code after you) -- you can generate the chain of "combinations()" generators, and iterate through that:

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) 
like image 78
Dan H Avatar answered Oct 10 '22 15:10

Dan H


Have a look at itertools.combinations:

itertools.combinations(iterable, r) 

Return r length subsequences of elements from the input iterable.

Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

Since 2.6, batteries are included!

like image 39
James Brady Avatar answered Oct 10 '22 13:10

James Brady