# Get list of all combinations from a set

Posted on

Problem

Given a tuple of elements, in `elementTupleParam` and the number in each combination `r`, we compute all the possible combinations of `r` elements, in a list of tuples. This is a recursive implementation.

One “challenge” is the inputs `r`, `n`, `elementTuple`, and the list holding the results, `combinationList`, are shared for all invocations of the recursive function. One method is to use global variables and bind them like below; which I think is rather ugly/bloated. Another method is to pass these are parameters to the recursive function, which may result in long parameter lists. Yet another is to make `partialCombinations` an inner function of `getCombinations`.

Another issue is the choice of data structure to hold the partial combinations and the result. I chose `tuple` because it’s immutable: `prevTuple` is shared across many subsequent invocations, and is less prone to errors caused by accidental modifications.

What do you think? Any thoughts on these or other aspects would be appreciated.

``````r = 0
n = 0
elementTuple = ()
combinationList = []

# get the vanilla combinations, nCr in number
def getCombinations(elementTupleParam, rParam):
global r
global n
global elementTuple
global combinationList

r = rParam
elementTuple = tuple(elementTupleParam)
n = len(elementTuple)
combinationList = []

if r == 0 or n == 0 or r > n:
return combinationList

partialCombinations((), -1)

return combinationList

def partialCombinations(prevTuple, prevVisitedIndex):
for thisIndex in range(prevVisitedIndex + 1, n):
thisTuple = prevTuple + (elementTuple[thisIndex],)

# If we exhausted all indices and have not formed a long enough tuple, then this is a dead-end, and don't do anything
if thisIndex == n - 1 and not len(thisTuple) == r:
continue

if len(thisTuple) == r: # Found combination
combinationList.append(thisTuple)
continue

partialCombinations(thisTuple, thisIndex)

#sanity check, should be moved to a unit test in another file
if __name__ == '__main__':
result = getCombinations((2,3,4), 2)
print(result)
``````

Solution

# Style

I suggest you check PEP0008 https://www.python.org/dev/peps/pep-0008/ the official Python style guide while writing your code and the following goes accordingly:

• Docstrings: Python Docstring is the documentation string which is string literal, and it occurs in the class, module, function or method definition, and it is written as a first statement. Docstrings are accessible from the doc attribute for any of the Python object and also with the built-in help() function can come in handy. I suggest you include docstrings to your functions indicating what they do and what they return instead of writing a comment above each function.
• Python naming conventions:

`def getCombinations(elementTupleParam, rParam):`

`def partialCombinations(prevTuple, prevVisitedIndex):`

Function names should be lowercase, with words separated
by underscores as necessary to improve readability same goes for
parameter names.

• Descriptive variable names: `thisIndex` `thisTuple` `prevTuple` are examples of bad non-descriptive names. Names should reflect the significance of the variable/function/parameter they represent and the less ambiguous they are, the more readable is your code.

# Code

• Global variables: are bad in Python and programming languages in general and are advised against. I suggest enclosing variables inside functions. The reason they are bad that they may allow functions to have hidden/hard to detect side effects leading to an increased complexity potentially leading to Spaghetti code. Examples of good use of global variables include: algorithm optimization – caching and memoization.
• There is a built-in Python library `itertools` that does the same functionality using `itertools.combinations()` which saves you the effort of implementing the thing yourself.

Code can be shortened into the following:
And according to GZO’s comment, there is no need for the warpper function `get_combinations()`, use `combinations()` directly. I included it just for the sake of the example.

``````from itertools import combinations

def get_combinations(n: list, r: int):
"""Return combinations iterator."""
return combinations(n, r)

if __name__ == '__main__':
print(list(get_combinations([2, 3, 4], 2)))
``````

Check these references(regarding global variables):

As pointed out by @bullseye, the `itertools` library provides `combinations()`.

If you are trying to learn how to implement your own version, here is a simple recursive version:

``````def combinations(seq, r):
"""returns a list of all r-length combinations of the elements of seq."""

if len(seq) == r:
# only one combination
return [seq]

elif r == 0:
# yield an empty seq of the same type as seq
return [seq[:0]]

else:
# combinations that _include_ seq[0]                    + those that exclude seq[0]
return [seq[:1] + tail for tail in combinations(seq[1:], r-1)] + combinations(seq[1:], r)
``````

Example:

``````combinations((1,2,3,4), 3), combinations('abcde', 3)
``````

Output:

``````([(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)],
['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde'])
``````

Here is an alternative version that generates the combinations lazily:

``````def combinations(seq, r):
if len(seq) == r:
# only one combination
yield seq

elif r == 0:
# yield an empty seq of the same type as seq
yield seq[:0]

else:
# yield all combinations that _include_ seq[0]
yield from (seq[:1] + tail for tail in combinations(seq[1:], r-1))

# yield all combinations that _exclude_ seq[0]
yield from combinations(seq[1:], r)
``````