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?
views:
429answers:
4
+7
A:
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.
If the OP only wants to know the number of combinations, then actually generating all of them is not the most efficient way to go about. </understatement>
Stephan202
2009-09-02 13:11:04
You say it: *if*
2009-09-02 13:11:50
Yes, that's what I want to do. Thank you.python is very powerful.btw, if I want to do the same thing in C++, Does it have a easy way to do so?
2009-09-02 13:24:43
Sorry, my C++ is ten years old :)
2009-09-02 13:25:59
@okman: The code for `itertools.combinations` is in the docs http://docs.python.org/library/itertools.html#itertools.combinations So you may be able to adapt it to C++. Or google around for "c++ permutations combinations".
John Fouhy
2009-09-03 02:24:25
C++ doesn't have a direct equivalent in the standard library. next_permutation comes pretty close but you still need to do some extra work. If performance isn't an issue then you can generate all permutations of 5 digits, discard the 2 trailing digits in each case, and then discard any duplicate entries.. (eg. http://www.cplusplus.com/reference/algorithm/next_permutation/) For combinations rather than all permutations
Kylotan
2009-09-03 10:17:47
+3
A:
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!)
Stephan202
2009-09-02 13:07:27
Still wrong. If I want to take 2 items from [1, 1, 2], there should be two distinct combinations.
recursive
2009-09-02 13:32:43
@recursive: you're right. I removed the remark (for now), because right now I am not able to figure out how the number of distinct combinations *should* be calculated.
Stephan202
2009-09-02 13:40:17
@Alec: that's what I initially wrote, yes, but it is incorrect (as recursive's example shows).
Stephan202
2009-09-02 13:58:01
+2
A:
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)]
>>>
gimel
2009-09-02 13:08:05