CODEWITHSUNDEEP
python
okman
okman

Reputation:

How to count possibilities in python lists

Given a list like this:

num = [1, 2, 3, 4, 5]

There are 10 three-element combinations:

[123, 124, 125, 134, 135, 145, 234, 235, 245, 345]

How can I generate this list?

Upvotes: 3

Views: 3249

Answers (4)

lutz
lutz

Reputation:

Use itertools.combinations:

import itertools

num = [1, 2, 3, 4, 5]
combinations = []
for combination in itertools.combinations(num, 3):
    combinations.append(int("".join(str(i) for i in combination)))
# => [123, 124, 125, 134, 135, 145, 234, 235, 245, 345]
print len(combinations)
# => 10

Edit

You can skip int(), join(), and str() if you are only interested in the number of combinations. itertools.combinations() gives you tuples that may be good enough.

Upvotes: 10

Stephan202
Stephan202

Reputation: 61529

You are talking about combinations. There are n!/(k! * (n - k)!) ways to take k elements from a list of n elements. So:

>>> num = [1, 2, 3, 4, 5]
>>> fac = lambda n: 1 if n < 2 else n * fac(n - 1)
>>> combos = lambda n, k: fac(n) / fac(k) / fac(n - k)
>>> combos(len(num), 3)
10

Use itertools.combinations only if you actually want to generate all combinations. Not if you just want to know the number of different combinations.

Also, there are more efficient ways to calculate the number of combinations than using the code shown above. For example,

>>> from operator import truediv, mul
>>> from itertools import starmap
>>> from functools import reduce
>>> combos = lambda n, k: reduce(mul, starmap(truediv, zip(range(n, n - k, -1), range(k, 0, -1))))
>>> combos(len(num), 3)
10.0

(Note that this code uses floating point division!)

Upvotes: 5

gimel
gimel

Reputation: 86362

itertools.combinations():

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.

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each combination.

>>> num = [1, 2, 3, 4, 5]
>>> [i for i in itertools.combinations(num,3)]
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5),
 (2, 4, 5), (3, 4, 5)]
>>>

Upvotes: 2

Adam Paynter
Adam Paynter

Reputation: 46908

I believe you are looking for the binomial coefficient:

Upvotes: 2

Related Questions