I'm trying to find a way to write a combination function. Where can I find it?
20
votes
3 Answers
25
votes
See in the documentation of itertools.combinations. There is an equivalent code for this function:
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
38
votes
0
votes
The while loop solution may be quite confusing... I wrote an "easier-to-understand" code using recursion. For every decision we make, we need to make more decisions until the combination reaches the length we desire (base case). Following is the code for itertools.combinations but considering that permutation is just an order-sensitive version of combinations, you can remove the sorting and hashset and easily make it an itertools.permuations method.
def combinations(curr, result, used):
if len(curr) == l:
result.add(tuple(sorted(curr))) #Modify this line to change it into itertools.permutations
return
else:
for i in arr:
if len(curr) == 0:
check_set = set()
else:
check_set = used
if i not in used:
temp = curr + [i]
check_set.add(i)
combinations(temp, result, check_set)