4
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ In those combinations, is order important? \$\endgroup\$
    – Gloweye
    Oct 2, 2019 at 8:17
  • \$\begingroup\$ @Gloweye No, it's not. \$\endgroup\$
    – flow2k
    Oct 2, 2019 at 8:30

2 Answers 2

5
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ Good call on using type hints for function parameters (even though they're just comments in Python). \$\endgroup\$
    – flow2k
    Oct 1, 2019 at 21:12
  • \$\begingroup\$ Thanks man, I hope i was of some help. \$\endgroup\$
    – watch-this
    Oct 1, 2019 at 21:16
  • \$\begingroup\$ There is no need for the wrapper function get_combinations function when combinations is used. \$\endgroup\$
    – GZ0
    Oct 1, 2019 at 22:22
  • \$\begingroup\$ @GZO I know, it's just for the sake of the example. \$\endgroup\$
    – watch-this
    Oct 1, 2019 at 22:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – Reinderien
    Oct 2, 2019 at 0:44
4
\$\begingroup\$

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)
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.