5
\$\begingroup\$

In Python, itertools.combinations yields combinations of elements in a sequence sorted by lexicographical order. In the course of solving certain math problems, I found it useful to write a function, combinations_by_subset, that yields these combinations sorted by subset order (for lack of a better name).

For example, to list all 3-length combinations of the string 'abcde':

>>> [''.join(c) for c in itertools.combinations('abcde', 3)]
['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']

>>> [''.join(c) for c in combinations_by_subset('abcde', 3)]
['abc', 'abd', 'acd', 'bcd', 'abe', 'ace', 'bce', 'ade', 'bde', 'cde']

Formally, for a sequence of length \$n\$, we have \$\binom{n}{r}\$ combinations of length \$r\$, where \$\binom{n}{r} = \frac{n!}{r! (n - r)!}\$

The function combinations_by_subset yields combinations in such an order that the first \$\binom{k}{r}\$ of them are the r-length combinations of the first k elements of the sequence.

In our example above, the first \$\binom{3}{3} = 1\$ combination is the 3-length combination of 'abc' (which is just 'abc'); the first \$\binom{4}{3} = 4\$ combinations are the 3-length combinations of 'abcd' (which are 'abc', 'abd', 'acd', 'bcd'); etc.

My first implementation is a simple generator function:

def combinations_by_subset(seq, r):
    if r:
        for i in xrange(r - 1, len(seq)):
            for cl in (list(c) for c in combinations_by_subset(seq[:i], r - 1)):
                cl.append(seq[i])
                yield tuple(cl)
    else:
        yield tuple()

For fun, I decided to write a second implementation as a generator expression and came up with the following:

def combinations_by_subset(seq, r):
    return (tuple(itertools.chain(c, (seq[i], ))) for i in xrange(r - 1, len(seq)) for c in combinations_by_subset(seq[:i], r - 1)) if r else (() for i in xrange(1))

My questions are:

  1. Which function definition is preferable? (I prefer the generator function over the generator expression because of legibility.)
  2. Are there any improvements one could make to the above algorithm/implementation?
  3. Can you suggest a better name for this function?
\$\endgroup\$
  • \$\begingroup\$ I think this ordering can be very useful and should be added to standard itertools library as an option. \$\endgroup\$ – mmj May 10 '16 at 22:24
7
\$\begingroup\$

Rather converting from tuple to list and back again, construct a new tuple by adding to it.

def combinations_by_subset(seq, r):
    if r:
        for i in xrange(r - 1, len(seq)):
            for cl in combinations_by_subset(seq[:i], r - 1):
                yield cl + (seq[i],)
    else:
        yield tuple()
\$\endgroup\$
0
\$\begingroup\$

I should preface with the fact that I don't know python. It's likely that I've made a very clear error in my following edit. Generally though, I prefer your second function to your first. If python allows, I would break it up a bit for readability. Why do I like it? It doesn't need the yield keyword and it's less nested.

# I like using verbs for functions, perhaps combine_by_subset()
# or generate_subset_list() ?
def combinations_by_subset(seq, r):
    return (

        # I don't know what chain does - I'm making a wild guess that
        # the extra parentheses and comma are unnecessary
        # Could this be reduced to just itertools.chain(c, seq[i]) ?

        tuple(itertools.chain(c, (seq[i], )))
            for i in xrange(r - 1, len(seq))
            for c in combinations_by_subset(seq[:i], r - 1)

        ) if r

    else ( () for i in xrange(1) )

I'm just waiting for this answer to get flagged as not being helpful. Serves me right for putting my two cents in when I don't even know the language. ;)

\$\endgroup\$
  • \$\begingroup\$ I would say the yield method is preferable because without yield you probably need to build an array (or some other data structure) in memory containing the entire data set, which may take up a lot of memory, or require a considerable amount of CPU power/time to generate. \$\endgroup\$ – borfast Dec 15 '14 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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