Get list of all combinations from a set

Question

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)

• Gloweye: In those combinations, is order important?
• flow2k: @Gloweye No, it's not.

Answer 1

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):

• https://softwareengineering.stackexchange.com/questions/148108/why-is-global-state-so-evil

• https://stackoverflow.com/questions/19158339/why-are-global-variables-evil

• flow2k: Good call on using type hints for function parameters (even though they're just comments in Python).
• watch-this: Thanks man, I hope i was of some help.
• GZ0: There is no need for the wrapper function get_combinations function when combinations is used.
• watch-this: @GZO I know, it's just for the sake of the example.
• Reinderien: main guard: shouldn't be moved to another file - This is not true. It's beneficial in a module for functions to be separated into separate files as logic and organization dictate. Often, a module's __main__.py will have little code other than an entry point.

Answer 2

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)