automatic "lotjes trekken"

[Tim Peters]

]François Pinard]
> Strange.  I was imagining you rather slim.  Are you? :-)

The adjective most people come up with first isn't "slim", but "shiny" --
such is the life of a bot.  BTW, I picture you as rather slim, since that's
how you picture me <wink>.

> By the way, I do not remember any standard library helper to enumerate
> all permutations (or combinations, or arrangements) of a given list
> (or tuple).  Ideally one at a time, of course.  Would this be useful?

It would (of course), and I don't know of any ready-made pkg either.  I've
likely got all the most useful algorithms coded up already (from
permutations of n things taken k at a time, to partitions of an integer, in
lexicographic or "Grey code" orderings).  They were written haphazardly as
needed over many years, though, and are inconsistent in their calling
conventions.  Several have been posted to c.l.py or one of the SIGs in
response to individual queries.  Someday I expect to clean 'em all up.

There is a particular irritation inherent in your natural generalization
from list to "list (or tuple)":  you should really add "(or sequence)",
including strings and user-defined sequence types.  A polymorphic generator
has to be written very carefully to work with all those types!  It also has
to be written inefficiently, since it can't assume the base sequence type is
mutable.  That is, about the only usable things all sequence types can be
expected to have in common are support for addition (+) and slicing
(seq[i:j]), so building up each intermediate result is generally
quadratic-time (repeated +).

In recent years, I've tended to ignore all that and write routines that
*just* work on lists.  Being able to mutate an indexed position can make
things much zippier, and having a notation for empty sequences ("[]") and
singletons ("[thing]") makes the code easier to follow.

Let's make that concrete.  I'll attach a CombGen class that works with any
sequence type, and where CombGen.get generates k-combinations one at a time
in lexicographic order, returning None after all possibilities have been
generated.  This is how it works:

>>> def exhaust(seq, k):
        g = CombGen(seq, k).get
        while 1:
            next = g()
            if next is None:
                break
            print next

>>> exhaust([1, 2, 3, 4], 3)
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
>>> exhaust((1, 2, 3, 4), 3)
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)
>>> exhaust("1234", 3)
123
124
134
234
>>>

That is, it dutifully returns k-combinations of the same sequence type as
the CombGen constructor's argument, but the code to achieve that is a bit
painful.  A CombGen that works only on lists can be much more efficient.

Another irritation is that the for/__getitem__ protocol isn't really suited
to this kind of application:  it's unnatural to index this kind of generator
by an integer.  So I write a lot of __getitem__ methods that ignore their
argument <0.5 wink>:

>>> def __getitem__(self, i): # all-purpose xxxGen __getitem__
        result = self.get()
        if result is None:
            raise IndexError
        return result

>>> CombGen.__getitem__ = __getitem__
>>> for comb in CombGen("abcd", 3):
        print comb
abc
abd
acd
bcd
>>>

overly-general-ly y'rs  - tim

class CombGen:
    def __init__(self, seq, k):
        n = self.n = len(seq)
        if not 1 <= k <= n:
            raise ValueError("k must be in 1.." + `n` + ": " + `k`)
        self.k = k
        self.seq = seq
        self.empty = seq[0:0]   # an empty sequence of this type
        self.indices = range(k)
        # Trickery to make the first .get() call work.
        self.indices[-1] = self.indices[-1] - 1

    def get(self):
        n, k, indices = self.n, self.k, self.indices
        lasti, limit = k-1, n-1
        while lasti >= 0 and indices[lasti] == limit:
            lasti = lasti - 1
            limit = limit - 1
        if lasti < 0:
            return None
        newroot = indices[lasti] + 1
        indices[lasti:] = range(newroot, newroot + k - lasti)
        # Build the result.
        result = self.empty
        seq = self.seq
        for i in indices:
            # There is no general way to spell "append an element to a
            # sequence"; addition requires two sequence arguments.
            result = result + seq[i:i+1]
        return result